KMP
问题：给定文本串S和模式串P，查找P在S中的位置
现在 S 匹配到了 i , P 匹配到了 j . 若 s [ i + 1 ] ! = p [ j + 1 ] , 需要重新匹配。
如果是暴力算法，需要重头匹配，真的有必要吗？
我们已知 i 匹配到了 j ,如果 有一个 k ,p [ 1 ~ k ] == p [ ( j - k + 1 )~j ]，就可以跳到 k 进行匹配，降低复杂度。
（这里应该有张图）
记一个 nxt 数组， nxt [ i ] 表示 p [ 1~i ] 的 最长公共前后缀， 求的方法和上面类似。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 const int N = 1000005; 7 char p[N],s[N]; 8 int nxt[N]; 9 int ls,lp; 10 inline void pre(){ 11 nxt[1]=0; 12 int j=0; 13 for(int i=2;i<=lp;i++){ 14 while(p[i]!=p[j+1]&&j)j=nxt[j]; 15 if(p[i]==p[j+1])++j; 16 nxt[i]=j; 17 } 18 } 19 inline void solve(){ 20 int j=0; 21 for(int i=1;i<=ls;i++){ 22 while(s[i]!=p[j+1]&&j)j=nxt[j]; 23 if(s[i]==p[j+1])++j; 24 if(j==lp){ 25 cout<<i-lp+1<<endl; 26 j=nxt[j]; 27 } 28 } 29 } 30 int main(){ 31 scanf("%s%s",s+1,p+1); 32 ls=strlen(s+1);lp=strlen(p+1); 33 pre(); 34 solve(); 35 for(int i=1;i<=lp;i++)cout<<nxt[i]<<" "; 36 }
复杂度O(N)
Trie
建树，边上是字母标号，沿着树边向下走，没有边了就新建。
Manacher
问题：对于一个字符串T，求出其最长回文子串。
回文串有奇回文串和偶回文串，为了保证回文串的回文中心都是字符，需要在每个字符后加一个其他字符（比如 ' $ '）；
假设求出了以 i 为中心的最长回文半径 R [ i ] ，对于在 [ i + 1， i + R [ i ] ] 内的点 q ,必定在 [ i - R [ i ] +1 ，i - 1 ] 有一个对应点 p ，且 R [ p ] 已经求出。
如果 R [ p ] 对称过来没有超出 ( i + R [ i ] )，显然可以。
超出来了就暴力嘛。
（这里应该有张图）
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 const int N = 11000005; 7 char s[N*2],c[N]; 8 int len,maxlen=0,R[N*2]; 9 int main(){ 10 scanf("%s",c+1); 11 len=strlen(c+1); 12 for(int i=1;i<=len*2+1;i++){ 13 if(i%2)s[i]='$'; 14 else s[i]=c[i/2]; 15 } 16 s[0]='%'; 17 int mx=0,id; 18 for(int i=1;i<=len*2+1;i++){ 19 if(i<mx)R[i]=min(R[2*id-i],mx-i); 20 else R[i]=1; 21 while(s[i-R[i]]==s[i+R[i]])R[i]++; 22 if(mx<i+R[i]){ 23 mx=i+R[i]; 24 id=i; 25 } 26 maxlen=max(maxlen,R[i]-1); 27 } 28 printf("%d",maxlen); 29 }
AC自动机（！=自动AC机）
问题：给m个模板串，用一个母串进行匹配。判断那些模板串在母串中出现过，出现了几次。
在trie上跑个KMP，对于每个节点求出失配指针，相当于nxt[]。
1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 const int N=1000005; 8 9 char ch[N<<1];//文本串 10 struct dot{ 11 int cnt,f,a[30];//f->fail 12 }t[N]; 13 int ans=0,tot=0; 14 queue<int> q; 15 char s[N]; 16 int n; 17 18 void build(){ 19 int len=strlen(s); 20 int j=0,now=0; 21 for(int i=0;i<len;i++){ 22 j=s[i]-'a'; 23 if(!t[now].a[j])t[now].a[j]=++tot; 24 now=t[now].a[j]; 25 } 26 t[now].cnt++; 27 } 28 29 inline void build_fail(){ 30 int now=0; 31 while(q.size())q.pop(); 32 for(int i=0;i<26;i++){ 33 int j=t[now].a[i]; 34 if(j){ 35 q.push(j); 36 t[j].f=now;//将第一层的f指向根 37 } 38 } 39 while(!q.empty()){ 40 now=q.front();q.pop(); 41 for(int i=0;i<26;i++){ 42 int j=t[now].a[i]; 43 if(!j){ 44 t[now].a[i]=t[t[now].f].a[i]; 45 //如果没有这个点，直接指向f的对应节点 46 continue; 47 } 48 t[j].f=t[t[now].f].a[i]; 49 //儿子的fail等于fail的儿子，对应KMP:nxt[i]=++j; 50 q.push(j); 51 } 52 } 53 } 54 55 inline void solve(){ 56 int now=0,len=strlen(ch); 57 for(int i=0;i<len;i++){ 58 int x=ch[i]-'a'; 59 int j=t[now].a[x]; 60 while(j&&t[j].cnt!=-1){//存在节点并未被统计 61 ans+=t[j].cnt; 62 t[j].cnt=-1; 63 j=t[j].f; 64 } 65 now=t[now].a[x]; 66 } 67 } 68 69 70 int main(){ 71 scanf("%d",&n); 72 while(n--){ 73 scanf("%s",s); 74 build(); 75 } 76 build_fail(); 77 scanf("%s",ch); 78 solve(); 79 printf("%d",ans); 80 }
（现在还在海亮，该补的图回去也不会补的）