本文共 3053 字，大约阅读时间需要 10 分钟。
KMP
略
Manacher
inline void manacher(){ int len=strlen(s); now[0]='!',now[1]='$',n=1; for(re int i=0;i
PAM
namespace PAM{ int nxt[N][27],fail[N],tot,len[N],s[N],cnt,last; inline void init(){ tot=1,fail[0]=1,len[1]=-1,s[0]=-1; } inline int find(int p,int k){ while(s[k-len[p]-1]!=s[k])p=fail[p]; return p; } inline void insert(int c){ s[++cnt]=c;int p=find(last,cnt); if(!nxt[p][c]){ fail[++tot]=nxt[find(fail[p],cnt)][c]; nxt[p][c]=tot,len[tot]=len[p]+2; } last=nxt[p][c]; }}
AC自动机
namespace AC{ int fail[N],end[N],nxt[N][26],tot; inline void insert(char c[],int p){ int len=strlen(c),u=0; for(int i=0;i q; for(int i=0;i<26;i++){
int v=nxt[0][i]; if(v)fail[v]=0,q.push(v); } while(!q.empty()){
int u=q.front();q.pop(); for(int i=0;i<26;i++){
int v=nxt[u][i]; if(v)fail[v]=nxt[fail[u]][i],q.push(v); else nxt[u][i]=nxt[fail[u]][i]; } } }}
统计时记得沿failfailfail跳所有子串
后缀数组+ST表
二分大法吼啊
namespace SA{ int n,m,sa[N],rk[N],cnt[N],sa2[N],st[22][N],ht[N],lg[N]; inline void bucsort(){ for(int i=1;i<=m;i++)cnt[i]=0; for(int i=1;i<=n;i++)cnt[rk[sa2[i]]]++; for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; for(int i=n;i>=1;i--)sa[cnt[rk[sa2[i]]]--]=sa2[i];//n->1 } inline void buildsa(){ m=128;// for(int i=1;i<=n;i++)rk[i]=a[i],sa2[i]=i; bucsort(); for(int i=1,pos;i<=n&&pos <<=1,pos=0){ pos=0; for(int j=n-i+1;j<=n;j++)sa2[++pos]=j;// for(int j=1;j<=n;j++)if(sa[j]>i)sa2[++pos]=sa[j]-i; bucsort(); swap(rk,sa2); rk[sa[1]]=1,pos=1; for(int j=2;j<=n;j++) rk[sa[j]]=((sa2[sa[j]]==sa2[sa[j-1]])&&(sa2[sa[j]+i]==sa2[sa[j-1]+i])?pos:++pos);//[j-1] m=pos; } for(int i=1;i<=n;i++)rk[sa[i]]=i; for(int i=1,k=0,j;i<=n;ht[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];a[j+k]==a[i+k];k++);//a,rk[i]-1 } void buildst(){ lg[0]=-1; for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++)st[0][i]=ht[i]; for(int i=1;(1< <=n;i++) for(int j=1;j+(1< <=n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]); } inline int lcp(int x,int y){ x=rk[x],y=rk[y]; if(x>y)swap(x,y);x++;//x+1 int t=lg[y-x+1]; return min(st[t][x],st[t][y-(1< SAM
namespace SAM{ int nxt[N][26],len[N],link[N],siz[N],tot,last; inline void init(){ last=tot=1; } inline void insert(int c){ int cur=++tot,p=last;last=cur; siz[cur]=1,len[cur]=len[p]+1;//p!=last for(;p&&!nxt[p][c];p=link[p])nxt[p][c]=cur; if(!p)link[cur]=1; else{ int q=nxt[p][c]; if(len[q]==len[p]+1)link[cur]=q; else { int clo=++tot; len[clo]=len[p]+1;link[clo]=link[q]; memcpy(nxt[clo],nxt[q],sizeof(nxt[q])); for(;p&&nxt[p][c]==q;p=link[p])nxt[p][c]=clo; link[q]=link[cur]=clo; } } } int A[N],B[N]; inline void getsiz(){ //维护endpos大小 for(int i=1;i<=tot;i++)A[len[i]]++; for(int i=1;i<=tot;i++)A[i]+=A[i-1]; for(int i=1;i<=tot;i++)B[A[len[i]]--]=i; for(int i=tot;i>=1;i--)siz[link[B[i]]]+=siz[B[i]]; }} 理解parent treeparent\ treeparent tree和DAGDAGDAG意义