本文共 8270 字，大约阅读时间需要 27 分钟。
之前一直跳过了字符串，现在才开始系统地学习，感觉需要记得模板挺多，在这里列个知识清单总结一下。
（1）字符串Hash
就是把字符串s视为一个B（一般B取不太大的质数）进制的数，用一个数组a来存s的前缀hash值，a用unsigned long long自动溢出比较方便。
一个重要的柿子：hash(s[l~r])=hash(s[r])-hash(s[l-1])*B^(r-l+1)
B的幂要预处理出来。
（2）Manacher
很NB的算法，要花点时间理解。
#include#include #include #include #include using namespace std;int Manacher(string &s){ string t="$#"; for(int i=0;i
（3）KMP
这个算法我起码学了3遍，还是经常忘。。。
这份代码s下标从1开始。
#include#include #include using namespace std;const int N=1e6+5;char A[N],B[N];int la,lb,nxt[N];void getnxt(){ nxt[1]=0; for(int i=2,j=0;i<=la;++i){ while(j&&A[i]^A[j+1]) j=nxt[j]; if(A[i]==A[j+1]) ++j; nxt[i]=j; }}int kmp(){ int ans=0; for(int i=1,j=0;i<=lb;++i){ while(j&&B[i]^A[j+1]) j=nxt[j]; if(B[i]==A[j+1]) ++j; if(j==la) ++ans,j=nxt[j]; } return ans;}int t;int main(){ cin>>t; while(t--){ scanf("%s %s",A+1,B+1); la=strlen(A+1),lb=strlen(B+1); getnxt(); printf("%d\n",kmp()); } return 0;}
（4）最小表示法
某些题目把形如“abcd”,“bcda”,"cdab","dabc"这些字符串（其实它们叫循环同构串）视为同一字符串，这时我们可以通过求出这些串的最小表示来提高比较和hash的效率。
这份模板代码s下标从1开始。
可以求出s的最小表示的起始位置。
int minpre(char *s){ int n=strlen(s+1); for(int i=1;i<=n;++i) s[n+i]=s[i]; int i=1,j=2,k; while(i<=n && j<=n){ for(k=0;k s[j+k]){ i=i+k+1; if(i==j) ++i; } else{ j=j+k+1; if(i==j) ++j; } } return min(i,j);} 给一道题目：
此题POJ上提交时记得选G++。
#include#include #include #include using namespace std;const int N=1e5+5,P=99991;inline int read(){ int x=0,w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return w?-x:x;} int n,tot,tmp[12],snow[N][12],tail[N],last[N],minl[N];int minprs(int *a){ int i=0,j=1,k; while(i<6&&j<6){ for(k=0;k<6&&a[i+k]==a[j+k];++k) ; if(k==6) break; if(a[i+k]>a[j+k]){ i=i+k+1; if(i==j) ++i; } else{ j=j+k+1; if(i==j) ++j; } } return min(i,j);}bool cmp(int pa,int *a,int *b){ int pb,pc,c[12]; for(int i=0;i<12;++i) c[11-i]=b[i]; pb=minprs(b),pc=minprs(c); bool ok=true; for(int i=0;i<6;++i) if(a[pa+i]^b[pb+i]) ok=false; if(ok) return true; ok=true; for(int i=0;i<6;++i) if(a[pa+i]^c[pc+i]) ok=false; if(ok) return true; return false;}int Hash(int *a){ int sum=0; for(int i=0;i<6;++i){ sum=(sum+a[i])%P; //mul=(long long)mul*a[i]%P; } return sum;} bool insert(int *a){ int val=Hash(a); for(int p=tail[val];p;p=last[p]) if(cmp(minl[p],snow[p],a)) return true; ++tot; for(int i=0;i<12;++i) snow[tot][i]=a[i]; minl[tot]=minprs(snow[tot]); last[tot]=tail[val]; tail[val]=tot; return false;}int main(){ n=read(); for(int i=1;i<=n;++i){ for(int j=0;j<6;++j) tmp[j]=tmp[j+6]=read(); if(insert(tmp)){ puts("Twin snowflakes found."); return 0; } } puts("No two snowflakes are alike."); return 0;}
（5）最小循环元
直接上柿子：
①如果(i-next[i])%i==0,那么(i-next[i])是s[1~i]的最小循环元长度.
②一个字符串的所有循环元长度都是最小循环元长度的倍数.
③把一个任意的s在添加字符最少的情况下补成一个循环同构串s'，设s的长度为len，那么有两种情况：
（i）next[i]=0 此时s自成s'的最小循环元，即需添加len个字符才能补成循环同构串.
（ii）next[i]≠0 此时s’的最小循环元长度为t=(len-next[len])，若(len%t==0)，s就等于s'，否则最少需添加（t-len%t）个字符才能补成循环同构串.
（6）Trie
这可能是最好理解的字符串算法之一了。
注意开数组时节点数应为（串的个数*串的最长长度）。
来个一般的模板：（）
#include#include #include #include using namespace std;const int N=1e5+5;inline int read(){ int x=0,w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return w?-x:x;}struct Trie{ int tot; bool mark[N]; int node[N][15]; void reset(){ tot=0; memset(mark,0,sizeof mark); memset(node,0,sizeof node); } bool insert(char *s){ int p=0; int l=strlen(s); for(int i=0;i
稍稍扩展一下，可以用Trie来搞异或和的问题。
看这道题：
建一棵以0为根的树，用d[i]表示从根节点到节点i路径上的异或和，可以知道对于任意两个节点i和j，它们之间路径的异或和就等于d[i]^d[j]。
那么问题转化成：在数组d中找两个数，使它们的异或值最大。
这可以用Trie解决。具体来说，把每个数视为32位的二进制串（不足在高位补0），建一棵01Trie树，然后对于每个数，在Trie树中尽量走与它的每一位相反的边（具体看代码）。
要注意高位补0是如何实现的，还有节点数应是（数的个数*32）。
#include#include #include #include using namespace std;const int N=1e5+5;inline int read(){ int x=0,w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return w?-x:x;} struct Graph{ struct Edge{ int v,w,last; }e[N<<1]; int tot,tail[N]; void clear(){ tot=0; memset(tail,0,sizeof tail); } void add(int x,int y,int z){ e[++tot]=(Edge){y,z,tail[x]}; tail[x]=tot; }}G;int n,d[N];void dfs(int x,int pre){ for(int p=G.tail[x];p;p=G.e[p].last){ int v=G.e[p].v,w=G.e[p].w; if(v^pre){ d[v]^=d[x]^w; dfs(v,x); } }}int tree[N<<5][2],tot;void insert(int x){ int p=1; for(int i=30;i>=0;--i){ int ch=(x>>i)&1; if(!tree[p][ch]){ tree[p][ch]=++tot; } p=tree[p][ch]; }}int search(int x){ int p=1,ans=0; for(int i=30;i>=0;--i){ int ch=(x>>i)&1; if(tree[p][ch^1]) p=tree[p][ch^1],ans|=(1<
再扩展一下，可以解决经典的哈夫曼编码问题，在此就不说了（这个人太懒了）。
（7）AC自动机
“至此，AC自动机终于揭开了“自动AC题目”的神秘面纱，向世人显露真容（滑稽）”
与我以往想象的不同，其实AC自动机非常好理解也非常好写。
挂一道几乎是模板题的代码：
#include#include #include #include using namespace std;const int N=255*1005;namespace AC{ //根节点是0 int mark[N]; int tree[N][26],fail[N],tot; void clear(){ tot=0; memset(mark,0,sizeof mark); memset(fail,0,sizeof fail); memset(tree,0,sizeof tree); } void insert(string s){ int p=0; for(int i=0;i
还有一道题： 里面我加了点优化（lst数组），就是把fail指针跳跃的路径给压缩了，实测时间可减少四分之一。
#include#include #include #include using namespace std;const int N=155,M=26;int n;string str,s[N];namespace AC{ int tot=0,fail[N*70],lst[N*70],mark[N*70],cnt[N],tree[N*70][M]; void clear(){ tot=0; memset(lst,0,sizeof lst); memset(cnt,0,sizeof cnt); memset(fail,0,sizeof fail); memset(tree,0,sizeof tree); memset(mark,0,sizeof mark); } void insert(string &s,int id){ int p=0; for(int i=0;i
（8）后缀数组
还没学。。。留个坑。
转载于:https://www.cnblogs.com/gosick/p/10628482.html