———————————————————–
后缀自动机
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void extend(int c) { int p=last,np;last=np=++cnt; maxlen[np]=maxlen[p]+1; while (!a[p][c]&&p) a[p][c]=np,p=fa[p]; if (!p) fa[np]=1; else { int q=a[p][c]; if (maxlen[q]==maxlen[p]+1) fa[np]=q; else { int nq=++cnt; maxlen[nq]=maxlen[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while (a[p][c]==q) a[p][c]=nq,p=fa[p]; } } } |
后缀数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
struct SA { char s[N]; int cnta[N],sa[N],rank[N*2],a[N],b[N],cntb[N],tsa[N],height[N]; void Get_SA() { for (int i=0;i<=256;i++) cnta[i]=0; for (int i=1;i<=n;i++) cnta[s[i]]++; for (int i=1;i<=256;i++) cnta[i]+=cnta[i-1]; for (int i=n;i>=1;i--) sa[cnta[s[i]]--]=i; rank[sa[1]]=1; for (int i=2;i<=n;i++) rank[sa[i]]=rank[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]); for (int i=1;rank[sa[n]]!=n;i<<=1) { for (int j=1;j<=n;j++) a[j]=rank[j],b[j]=rank[j+i]; for (int j=0;j<=n;j++) cnta[j]=0,cntb[j]=0; for (int j=1;j<=n;j++) cnta[a[j]]++,cntb[b[j]]++; for (int j=1;j<=n;j++) cnta[j]+=cnta[j-1],cntb[j]+=cntb[j-1]; for (int j=n;j>=1;j--) tsa[cntb[b[j]]--]=j; for (int j=n;j>=1;j--) sa[cnta[a[tsa[j]]]--]=tsa[j]; rank[sa[1]]=1; for (int j=2;j<=n;j++) rank[sa[j]]=rank[sa[j-1]]+(a[sa[j]]!=a[sa[j-1]]||b[sa[j]]!=b[sa[j-1]]); } } void Get_Height() { int len=0; for (int i=1;i<=n;i++) { if (len) len--; while (s[i+len]==s[sa[rank[i]-1]+len]) len++; height[rank[i]]=len; } } }S; |
manacher
1 2 3 4 5 6 7 8 9 10 11 |
void manacher() { int maxright=0,pos=0; for (int i=1;i<=n;i++) { if (i<=maxright) RL[i]=min(RL[pos+pos-i],maxright-i); else RL[i]=1; while (s[i-RL[i]]==s[i+RL[i]]) RL[i]++; if (i+RL[i]>maxright) maxright=i+RL[i],pos=i; } } |
KMP
1 2 3 4 5 6 7 8 9 10 |
void Get_Next() { fail[0]=-1; for (int i=1;i<=n;i++) { int id=fail[i-1]; while (id!=-1&&s[i]!=s[id+1]) id=fail[id]; fail[i]=id+1; } } |
AC自动机
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void build_fail() { fail[1]=0; for (int i=0;i<26;i++) a[0][i]=1; int t=0,w=1; Q[1]=1; while (t<w) { int u=Q[++t]; for (int i=0;i<26;i++) if (a[u][i]) { fail[a[u][i]]=a[fail[u]][i]; Q[++w]=a[u][i]; }else a[u][i]=a[fail[u]][i]; } } |
Orz
SAM,SA大佬
PAM回文自动机了解一下
我太菜了,我不会啊。