##浅谈字符串算法 ##

一、KMP

KMP算法是一种用于处理字符串匹配的算法（也就是给你两个字符串，你需要回答，B 串是否是 A 串的子串（A 串是否包含 B 串）。比如，字符串 A=“I love the world”，字符串 B=“world”，我 们就说 B 是 A 的子串。我们称等待匹配的 A 串为主串（母串），用来匹配的 B 串为模式串）

对于一般情况来讲，我们可以直接对AB两串暴力匹配，最坏情况的复杂度为O（mn)，而KMP是一种最坏情况复杂度为O（max（m，n））的算法。

对于$A[1...i]$和$B[1...j]$($i>j$)两个字符串，如果$A[u-v+1...u]$和$B[1...v]$都是相匹配的，但在$A[u+1]$和$B[v+1]$时失配了，那么我们通过减小$v$的值使得$A[u-v+1...u]$和$B[1...v]$相匹配并尝试新的$A[u+1]$和$B[v+1]$。

那么我们怎么减小v的值？如果每次减1的话对于复杂度来说并没有什么优化，所以说我们需要一个next数组来记录上一个能够匹配的地方（或者记录和上一个能匹配的地方的距离），然后发现这和KMP的匹配好像是一个意思，只是一个是两个之间的匹配，一个是一个串自己的匹配

时间复杂度是O（max（m，n））的，可以证明

因为每一次执行while循环都会使 j 的值减小，而总共 j 只会减少n次，按照摊还分析的说法，平均分配到每一次循环中，复杂度是O（1）的，（有的会多一些，但有些也相应不会），所以总复杂度为O（max（m，n）），而预处理的复杂度为O（min（m，n））；

具体参考代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;char a[1000005],b[1000005];int next[1000005];bool ans;int main(){ cin>>a+1; cin>>b+1; int m=strlen(a+1); int n=strlen(b+1); //预处理next数组，b[i]和b[j]自我匹配 for(int i=2,j=0;i<=n;i++){ while(j>0&&b[j+1]!=b[i]) j=next[j]; if(b[j+1]==b[i]) j++; next[i]=j; } ans=false; //KMP算法 for(int i=1,j=0;i<=m;i++) { while(j>0&&b[j+1]!=a[i]) j=next[j]; if(b[j+1]==a[i]) j++; if(j==n) cout<
          
           <
          
         
        
       
      
     
    

字典树

字典树，也称 Trie、字母树，指的是某个字符串集合对应的形如下图的有根树。一般树的每

条边上对应有恰好一个字符，每个顶点代表从根到该节点的路径所对应的字符串（将所有经

过的边上的字符按起来）

Trie树一般用于字符串的查找，匹配，能统计，排序，保存大量字符串信息，时间效率相当优秀（当然是以空间复杂度为代价的）

如果字符串为小写字母的话，字典树可以看成一个26叉树，而树的公共前缀可以很好的节省空间，插入和查询操作和树一样，一直往下走就了。

字典树主要的两种操作就是插入和查询，都是很简单的在树下走就是了

我们通过一个结构体来储存一个节点的信息：$trans[i]$以i为边的儿子的编号，一个bool变量bo 记录是否为一个字符串的结尾

插入操作

void insert(char *s) { 	int len = strlen(s); 	int u = 1; // 1 为根节点 	for (int i = 0; i < len; ++i) { 		if (!tr[u].trans[s[i] - 'a']) // 若不存在这条边则要新建一个节点与转移边 			tr[u].trans[s[i] - 'a'] = ++tot; // tot 为总点数 		u = tr[u].trans[s[i] - 'a']; 	} 	tr[u].bo = true; // 在串的结尾处将 bo 赋值，表示它代表一个实际字符串

查询操作

bool insert(char *s) { 	int len = strlen(s); 	int u = 1; 	for (int i = 0; i < len; ++i) { 		if (!tr[u].trans[s[i] - 'a']) return false; 		u = tr[u].trans[s[i] - 'a']; 	}	 	return true; }

AC自动机

AC自动机其实和是Trie树和KMP的综合体，用于处理多模式匹配，比如说，给你N个串，再给你一片文章，问多少个个串在文章里出现了。

AC自动机相当于在Trie树上做匹配，而为了减小复杂度，利用和KMP相似的思想构建一个失败指针（fail）（相当于KMP里的next数组）来减小时间复杂度，不过KMP里是在一个串上不断地跳，而AC自动机是在整个Trie树上不断地跳

对于一个点u，我们需要找到一个点v使v所代表的串有尽量长的前缀和u的后缀相等，显然这个v节点的深度是小于u节点的，因此我们可以通过按节点的深度大小，也就是 BFS 的顺序来构建失配指针，构建过程与 KMP 类似，KMP 中i的 next 是沿着 1 i 的 next 不 停往前跳来求，而 AC 自动机中u的 fail 则通过父节点的 fail 不停往上跳，直到找到一个节点

它拥有对应字符的转移边为来得

代码

#include
    
     using namespace std; const int n = 10000 + 3; const int m = 1e6 + 3; const int l = 50 + 3;  int t,tot,k,vst[n*l]; struct node{ 	int cnt,fail; 	int trans[26]; 	void init(){ 		cnt=fail=0; 		memset(trans,0,sizeof(trans)); 	} }tr[n*l]; char s[m]; void insert(char *s){ 	int len=strlen(s); 	int u=1; 	for(int i=0;i
     
      >t; 	 for(int tt=1;tt<=t;++tt){ 	 	tr[tot=1].init(); 	 	cin>>k; 	 	for(int i=1;i<=k;++i){ 	 		cin>>s; 	 		insert(s); 	 	} 	 	buildfail(); 	 	cin>>s; 	 	int len=strlen(s); 	 	int now=1,tmp,ans=0; 	 	for(int i=0;i