【学习笔记】字符串算法汇总
【大前言】
\(To\) \(be\) \(continued...\)
\[QAQ\]
一.【字符串哈希(Hash)】
\(To\) \(be\) \(continued...\)
\[QAQ\]
二.【最小表示法】
\(To\) \(be\) \(continued...\)
\[QAQ\]
三.【Kmp】
看毛片。
\(To\) \(be\) \(continued...\)
\[QAQ\]
四.【扩展Kmp(ExKmp)】
儿想看毛片。
\(To\) \(be\) \(continued...\)
\[QAQ\]
五.【马拉车(Manacher)】
1.【前言】
马拉车用于求解连续回文子串问题,效率极高。
其核心思想与 \(kmp\) 类似:继承。 ——引自 \(yyx\) 学姐
2.【算法原理】
对于任意一个回文串 \(a\),设其中点为 \(mid\)(为方便描述,偶数串则在正中央加一个位置),那么根据定义,有:
\(a[mid-1]==a[mid+1]\)
\(a[mid-2]==a[mid+2]\)
\(...\)
可知:
如果 \(a[mid-x]\) 可以形成半径为 \(r\) 的回文串,且不越过以 \(mid\) 为中心的回文串,那么 \(a[mid+x]\) 也可以形成半径为 \(r\) 的回文串。
以奇回文串为例,用 \(r[i]\) 表示以 \(i\) 为中点的最大回文串长度。
如果我们已知 \(r[mid],r[j](j \in [mid-r[mid]+1,mid-1])\),那么可以分两种情况推出其关于 \(mid\) 的对称点 \(i\) \((\frac {i+j}{2}=mid)\) 的半径:
设 \(R=mid+r[mid]-1\) 。
\((1).\) \(i+r[j]-1<=R,\) \(r[i]=r[j]\) 。
\((2).\) \(i+r[j]-1>R,\) \(r[i]=R-i+1\) 。
即 \(r[i]=min(r[j],R-i+1)\) 。
如上所述,实现了从前面信息到后面信息的继承。
继承之后还需要判断以 \(i\) 为中心能否继续扩张,这时候可以直接暴力枚举扩大半径。
3.【算法实现】
实时维护一个已知覆盖范围最靠右的回文串信息,记录其中点 \(mid\) 和右端点 \(R\)。
从 \(1,n\) 枚举 \(i\):
若 \(i<=R\) 则可以用 \(i\) 的对称点 \(mid*2-i\) 得到 \(r[i]\),
若 \(i>R\)(即 \(R=i-1\) 的情况,因为 \(R\) 永远大于等于 \(i-1\)),初始化 \(r[i]=1\),然后暴力扩大求出最大 \(r[i]\)。
如果以 \(i\) 为中点可以得到更靠右的回文串,更新 \(mid\) 和 \(R\)。
但偶数串不太好处理,所以在原字符串中的所有空隙中插入一个不可能出现的字符,例如 \('*',\) \('|'\) 等等,最前面和最后面也要插。
此时,奇数串还是奇数串,偶数串则变成了奇数串,可以统一按照奇数串处理啦。
注意:统计答案时应取真实的回文串长度。
(具体可以自己画个图分类讨论一下,会发现无论奇偶,无论是否为原字符串中的字符,\(r[i]-1\) 始终等于以 \(i\) 为中点的实际最大回文串长度。)
【Code】
题目:\(Palindrome\) \([Poj3974]\)
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
#define Re register int
using namespace std;
const int N=1e6+5;
int n,R,mid,ans,OOO,r[N<<1];char op[N],a[N<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
while(cin>>op){
if(op[0]=='E'&&op[1]=='N'&&op[2]=='D')break;//没用string就只能这样一位一位地判断了
a[0]='$',a[n=1]='*',R=0,mid=0,ans=0;
for(Re i=0;op[i];++i)a[++n]=op[i],r[n]=0,a[++n]='*',r[n]=0;//玄学填空法
for(Re i=1;i<=n;++i){
r[i]=i<=R?min(R-i+1,r[(mid<<1)-i]):1;//继承前辈的信息
while(a[i-r[i]]==a[i+r[i]])++r[i];//暴力扩张领域
if(i+r[i]-1>R)R=i+r[mid=i]-1;
ans=max(ans,r[i]-1);//取实际回文长度
}
printf("Case %d: %d\n",++OOO,ans);
}
}
4.【时间复杂度】
似乎看起来效率并不高,近似 \(O(n^2)\),但实际上它的理论复杂度是 \(O(n)\)。
为何?
对于每个 \(i\):
如果 \(i<=R\),那么直接 \(O(1)\) 计算 \(r[i]\)。
如果 \(i>R\),那么会用 \(O(len)\) 向右扫描 \(len\)个单位,所以此时 \(R\) 会向右移动 \(len+1\) 的单位。
而 \(R\) 最多只会移动 \(n\) 个单位,因此 \(Manacher\) 算法时间复杂度是线性的:\(O(n)\)。
【例题】
【模板】\(manacher\) 算法 \([P3805]\)
【标签】字符串/回文串/\(Manacher\) 模板- \(Palindrome\) \([Poj3974]\)
【标签】字符串/回文串/\(Manacher\) 模板/\(Hash\)/二分 \(Palindrome\) \(pairs\) \([CF159D]\)
【标签】字符串/回文串/\(Manacher\)/差分
【题解】\(Xing\)_\(Ling\)\(Sonya\) \(and\) \(Matrix\) \(Beauty\) \([CF1080E]\)
【标签】字符串/回文串/\(Manacher\)/暴力枚举/整体思想
【题解】\(Xing\)_\(Ling\)
\[QAQ\]
六.【字典树(Trie)】
\(To\) \(be\) \(continued...\)
\[QAQ\]
七.【AC自动机】
在树上看毛片(\(Tire\) 树)。
\(To\) \(be\) \(continued...\)
\[QAQ\]
八.【后缀数组】
\(To\) \(be\) \(continued...\)
\[QAQ\]
九.【后缀自动机(SAM)】
\(To\) \(be\) \(continued...\)
\[QAQ\]
十.【回文自动机/回文树(PAM)】
\(To\) \(be\) \(continued...\)
\[QAQ\]