哈希
双模数更稳一些。不要忘记可以哈希
KMP
int nxt[N];
void getnxt(char s[],int n){
int k=0; nxt[1]=0;
for(int i=2;i<=n;i++){
while(k && s[i]!=s[k+1]) k=nxt[k];
if(s[i]==s[k+1]) k++;
nxt[i]=k;
}
}
整个串的最短循环节为 (n-nxt[n])
更多推荐以前的博客
扩展KMP（Z函数）
作用：求字符串 (T) 的每一个后缀与 (S) 的最长公共前缀长度。
借助数组 (nxt[]) 表示 (S) 的每个后缀与 (S) 的最长公共前缀长度 求 数组 (ext[]) 表示 (T) 的后缀与 (S) 的最长公共前缀长度。
两者求法类似
保存当前最远距离 (p) 与达到最远距离的点 (q) ，分类讨论……
char s[N],t[N];
int nxt[N],ext[N],n,m;
void getnxt(){
int p=0,q=0;
nxt[1]=n;
for(int i=2;i<=n;i++){ //n! not m!
if(i<=p) nxt[i]=min(nxt[i-q+1],p-i+1);
while(i+nxt[i]<=n && s[i+nxt[i]]==s[1+nxt[i]]) ++nxt[i];
if(i+nxt[i]-1>p) p=i+nxt[i]-1,q=i;
}
}
void getext(){
int p=0,q=0;
for(int i=1;i<=m;i++){
if(i<=p) ext[i]=min(nxt[i-q+1],p-i+1);
while(i+ext[i]<=m && 1+ext[i]<=n && s[1+ext[i]]==t[i+ext[i]]) ++ext[i];
if(i+ext[i]-1>p) p=i+ext[i]-1,q=i;
}
}
trie树
在字符串中的作用是可以在上面 (dp) ？
规模小的时候用它挺方便
(01-trie) 在二进制方面比较有用
AC自动机
(KMP+trie) ，重要的是 (fail) 指针，这些 (fail) 构成 (fail) 树
毕竟是自动机嘛，天然方便 (dp) 的进行
写法不少，但比较方便的是在 (getfail) 时直接把没有的节点赋成匹配时将要去的下一个节点
int cnt,root,ch[N][26],fail[N],pa[N],End[N];
void ins(char s[],int n,int id){
int x=root;
for(int i=1;i<=n;i++){
if(!ch[x][s[i]-'a']) ch[x][s[i]-'a']=++cnt,pa[cnt]=x;
x=ch[x][s[i]-'a'];
}
End[id]=x;
}
int hd,tl,que[N];
void getfail(){
hd=tl=0;
fail[root]=root;
for(int i=0;i<26;i++)
if(ch[root][i])
fail[ch[root][i]]=root,que[tl++]=ch[root][i];
else ch[root][i]=root;
while(hd<tl){
int x=que[hd++],y=fail[x];
for(int i=0;i<26;i++)
if(ch[x][i]){
fail[ch[x][i]]=ch[y][i];
que[tl++]=ch[x][i];
}
else ch[x][i]=ch[y][i];
}
}
后缀数组SA
后缀数组的应用：利用 (SA) 是有序的——用来比较串的大小；在字典序中二分找子串……
结合 (height) 数组的应用:
- 两个串最长公共前缀：找到两个串在 (sa) 中的位置，求中间 (h) 的最小值
- 求不同子串个数：利用 (h) 找每次新增的子串
- 求至少出现 (k) 次的最长子串：在 (h) 上单调栈，每次找相邻 (k) 个中的 (h) 最小值
- 是否有不重叠出现两次的子串：二分子串长度 (L)，把 (h) 分段，每段最小值 (geq L) ，看每段是否满足子串不重叠
- 多个子串问题：中间用特殊符号连接，求 (sa,h) ，利用 (h) 求解
- 结合数据结构，线段树、并查集等
char s[N];
int sa[N],cnt[N],rk[N],y[N],n;
void SA(){
int m=80;
for(int i=1;i<=m;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[s[i]-'0'+1]++;
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;i++) rk[i]=s[i]-'0'+1,sa[cnt[rk[i]]--]=i;
for(int k=1;k<n;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;i++) y[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
for(int i=1;i<=m;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[rk[i]]++;
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--) sa[cnt[rk[y[i]]]--]=y[i];
for(int i=1;i<=n;i++) y[i]=rk[i];
p=0; rk[sa[1]]=++p;
for(int i=2;i<=n;i++)
if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])
rk[sa[i]]=p;
else rk[sa[i]]=++p;
m=p;
}
}
int h[N];
void geth(){
for(int i=1;i<=n;i++){
int k=max(0,h[rk[i-1]]-1),j=sa[rk[i]-1];
if(rk[i]==1) { h[rk[i]]=0; continue; }
for(;i+k<=n && j+k<=n && s[i+k]==s[j+k];k++);
h[rk[i]]=k;
}
}
后缀自动机SAM
后缀自动机
转移边构成 (DAG) ，(pa) 构成树
作用太多了……一个套路是可持久化线段树合并维护 (right) 集合，时空复杂度都是 (O(nlogn)) ，但注意数组要开够 (大概 (2nlogn) ?)
应用：
- 求不同子串个数：(DAG) 上 (dp) 求不同路径数目 (or) 所有点的 (len[i]-len[pa[i]]) 加起来
- 检测子串是否出现：直接自动机上跑
- 第 (k) 大子串：预处理每个点往后多少串然后跑
- 最小循环子串：(S+S) 建后缀自动机，贪心跑可以跑的最小字符
- 最长公共子串：对匹配串的每个前缀求最长可匹配的后缀（(SAM) 上跑，时时维护 (len) ）
……
int root,last,cnt1,ch[N*2][26],len[N*2],pa[N*2];
void insert(int c){
int x=last,cur=++cnt1;
len[cur]=len[x]+1;
add(rt[cur]=++cnt,1,n,len[cur]);
for(;x && !ch[x][c];x=pa[x]) ch[x][c]=cur;
if(!x) pa[cur]=root;
else{
int y=ch[x][c],ny;
if(len[y]==len[x]+1) pa[cur]=y;
else{
ny=++cnt1;
len[ny]=len[x]+1;
for(int i=0;i<26;i++) ch[ny][i]=ch[y][i];
pa[ny]=pa[y]; pa[y]=pa[cur]=ny;
for(;x && ch[x][c]==y;x=pa[x]) ch[x][c]=ny;
}
}
last=cur;
}
广义后缀自动机
据说有 (trie) 树上后缀自动机，但我不会……
会的一直是假假广义后缀自动机，就是插完一个串后指针指回 (root)
Manacher
求以每个点（或空隙）为回文中心的最长回文子串
做法跟扩展 (KMP) 有点像…保存当前已到的最远位置和对应的中心点，利用对称过去记过的信息更新
注意要先在原串的首尾即各个字符之间插上特殊字符 $ $ $
求数组 (mx[i]) 表示以新串中第 (i) 位为中心往两侧扩展，一侧的最远距离（包括自己）
那么原串以 (i) 为中心的回文子串长度为 (mx[i]-1)
void manacher(){
mx[1]=1;
for(int i=2,p=1,q=1;i<=m;i++){
if(i<=p) mx[i]=min(mx[2*q-i],p-i+1);
else mx[i]=1;
while(i+mx[i]<=m && i-mx[i]>0 && s[i-mx[i]]==s[i+mx[i]]) mx[i]++;
if(i+mx[i]-1>p) p=i+mx[i]-1,q=i;
}
}
主函数中处理得出新串：
scanf("%s",a+1); n=strlen(a+1);
m=0; s[++m]='$';
for(int i=1;i<=n;i++) s[++m]=a[i],s[++m]='$';
回文自动机
每个节点表示一个回文串，维护 (fail) 表示每个回文串的最长回文后缀（最长回文前缀（一样的））
有两个根，奇根和偶根，奇根的长度为 (-1) ，偶根的 (fail) 指向奇根
增量法构造
也有 (fail) 树的概念
int cnt,last,ch[N][26],fail[N],len[N],num[N];
void init(){
len[0]=0; len[1]=-1;
fail[0]=fail[1]=1;
num[0]=num[1]=0;
last=++cnt;
}
void ins(int c,int i){
int x=last;
for(;s[i]!=s[i-1-len[x]];x=fail[x]);
if(ch[x][c]) { last=ch[x][c]; return; }
int y=++cnt,k=fail[x];
for(;s[i]!=s[i-1-len[k]];k=fail[k]);
fail[y]=ch[k][c]; num[y]=num[fail[y]]+1;
len[y]=len[x]+2; ch[x][c]=y;
last=y;
}
其实是可以双向加的，因为 (fail) 表示的既是最长回文前缀也是最长回文后缀
只需维护两个 (llast)，(rlast) 表示往两侧加时包括最后加的那个点的最长回文串
注意要时时更新，比如往右加发现整个串变成回文串后，(llast) 也要更新成新的那个点
int cnt,len[N],fail[N],ch[N][26],llast,rlast,dep[N];
void init(){
len[0]=0; len[1]=-1;
fail[0]=fail[1]=1;
cnt=1; llast=rlast=1;
L=N; R=N-1;
}
void ins_front(int c){
s[--L]='a'+c;
int x=llast;
for(;s[L]!=s[L+len[x]+1];x=fail[x]);
if(ch[x][c]) { llast=ch[x][c]; return; }
int y=++cnt,k=fail[x];
for(;s[L]!=s[L+len[k]+1];k=fail[k]);
fail[y]=ch[k][c];
len[y]=len[x]+2; dep[y]=dep[fail[y]]+1;
ch[x][c]=y;
llast=y;
if(len[y]==R-L+1) rlast=llast; /**/
}
void ins_back(int c){
s[++R]='a'+c;
int x=rlast;
for(;s[R]!=s[R-len[x]-1];x=fail[x]);
if(ch[x][c]) { rlast=ch[x][c]; return; }
int y=++cnt,k=fail[x];
for(;s[R]!=s[R-len[k]-1];k=fail[k]);
fail[y]=ch[k][c];
len[y]=len[x]+2; dep[y]=dep[fail[y]]+1;
ch[x][c]=y; /**/
rlast=y;
if(len[y]==R-L+1) llast=rlast; /**/
}