Codeforces 961F - k-substrings(二分+哈希)
介绍一种奇怪的 \(\Theta(n\log n)\) 的奇怪做法。
注意到这个“border 的长度必须是奇数”的条件非常奇怪,同时我们待求解的字符串也有一些比较奇妙的性质——它们的左右端点都关于中线轴对称,即 \(l+r=n+1\)。我们考虑 border 的性质与 \(l+r=n+1\) 的条件联系起来。对于一个 \(s[l...r]\) 的长度为 \(len\) 的 border(\(len\) 为奇数),假设 \(r'=l+len-1,l'=r-len+1\),那么必然有 \(s_l\) 与 \(s_{l'}\)、\(s_{l+1}\) 与 \(s_{l'+1}\),……,\(s_r\) 与 \(s_{r'}\) 均匹配。在下文中,用“左 border”代替 \(s[l...r']\),“右 border”代替 \(s[l'...r]\)。
然后我们惊奇地发现,如果我们记 \(m_l=\dfrac{l+r'}{2},m_r=\dfrac{l'+r}{2}\),那么有 \(m_l+m_r=n+1\),并且 \(m_l\) 与 \(m_r\) 也应匹配。画出图来大概是这个样子,其中黑线为中线 \(\dfrac{n+1}{2}\),绿线为左 border 的两个端点,褐色的线为右 border 的两个端点:
因此我们考虑枚举 \(m_l\),那么可以发现,由于 \(m_l\) 是左 border 的中点,\(m_r\) 是右 border 的中点,因此在上图中,两段黄色部分对应的字符串必须相同,两段紫色部分也同理,并且黄色和紫色部分长度也应相同。也就是说 \(s[l...m_l],s[l'...m_r]\) 是 \(s[1...m_l],s[1...m_r]\) 两段前缀的 LCS,\(s[m_l...r'],s[m_r...r]\) 是 \([l...n],s[r...n]\) 的两段后缀的 LCP,也就是说,我们可以通过二分+哈希找到 \(s[l...m_l]\) 这段区间的范围,不妨设其为 \([1,mn]\)。得到了这些信息之后,又该怎样求解答案呢?对于每个左端点 \(l\),我们考虑设 \(M_l\) 表示 \([l,n+1-l]\) 的所有长度为奇数的 border 中,左 border 的中点的最大值,显然只要左 border 的中点越靠右,对应的 border 长度也就越大,而不难发现,我们求出 \(m_l,m_r\) 可以延伸的范围 \([1,mn]\) 之后,操作等价于令 \(M_{m_l-mn+1},M_{m_l-mn+2},\cdots,M_{m_l}\) 均对 \(m_l\) 取 \(\max\),差分一下用个 set
维护即可。
const int MAXN=1e6;
const int MOD=1004535809;
const int BS=193;
int n;char s[MAXN+5];
int pw[MAXN+5],hsh[MAXN+5];
vector<int> add[MAXN+5],del[MAXN+5];
int gethsh(int l,int r){return (hsh[r]-1ll*hsh[l-1]*pw[r-l+1]%MOD+MOD)%MOD;}
int main(){
scanf("%d%s",&n,s+1);
for(int i=(pw[0]=1);i<=MAXN;i++) pw[i]=1ll*pw[i-1]*BS%MOD;
for(int i=1;i<=n;i++) hsh[i]=(1ll*hsh[i-1]*BS+s[i])%MOD;
for(int i=1;i<=n>>1;i++) if(s[i]==s[n+1-i]){
int l=1,r=i,L=0,R=0;
while(l<=r){
int mid=l+r>>1;
if(gethsh(i-mid+1,i)==gethsh(n+1-i-mid+1,n+1-i)) L=mid,l=mid+1;
else r=mid-1;
} l=1,r=i;
while(l<=r){
int mid=l+r>>1;
if(gethsh(i,i+mid-1)==gethsh(n+1-i,n-i+mid)) R=mid,l=mid+1;
else r=mid-1;
} int mn=min(L,R);
add[i-mn+1].pb(i);del[i+1].pb(i);
} multiset<int> st;
for(int i=1;i<=(n+1>>1);i++){
for(int x:add[i]) st.insert(x);
for(int x:del[i]) st.erase(st.find(x));
if(st.empty()) printf("-1 ");
else printf("%d ",((*st.rbegin())-i+1)*2-1);
}
return 0;
}
最新文章
- zookeeper学习系列:四、Paxos算法和zookeeper的关系
- 修改Android系统属性SystemProperties.set(";sys.powerctl";, ";shutdown";)关机分析
- Ubuntu学习——第一篇
- 14个HTML5实现的效果合集
- install gcc under suse
- 安装phonegap
- MQ学习(一)----JMS规范(转发整合)
- python自学笔记(二)python基本数据类型之字符串处理
- filter的两种使用方法
- ServerSocket(TCP/IP协议)__Java
- hdu3340 线段树+多边形
- 解决github下载速度慢的问题 ,亲测有效
- vue中less文件全局引用
- Mysql数据库多表查询
- nodeJS之crypto模块公钥加密及解密
- 20165313 《Java程序设计》第六周学习总结
- Hadoop hostname: Unknown host
- OpenCV实现SfM(三):多目三维重建
- pymysql模块操作数据库
- [面试]CVTE 2019提前批 Windows应用开发一面
热门文章
- Flask的环境配置
- 什么是产品待办列表?(What is Product Backlog)
- 安装多个版本的MySQL
- Beta阶段第六次会议
- vim 让人爱不释手的编辑器之神
- CLion 2021.2 debug报错 process exited with status -1 (attach failed (Not allowed to attach to process.
- VSCode PHP 开发环境配置 详细教程
- 使用 SSL 加密的 JDBC 连接 SAP HANA 数据库
- Linux 下权限的管理
- Vue3+Vue-cli4项目中使用腾讯滑块验证码