##浅谈字符串算法 ##
一、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））的算法。
对于和()两个字符串，如果和都是相匹配的，但在和时失配了，那么我们通过减小的值使得和相匹配并尝试新的和。
那么我们怎么减小v的值？如果每次减1的话对于复杂度来说并没有什么优化，所以说我们需要一个next数组来记录上一个能够匹配的地方（或者记录和上一个能匹配的地方的距离），然后发现这和KMP的匹配好像是一个意思，只是一个是两个之间的匹配，一个是一个串自己的匹配
时间复杂度是O（max（m，n））的，可以证明
因为每一次执行while循环都会使 j 的值减小，而总共 j 只会减少n次，按照摊还分析的说法，平均分配到每一次循环中，复杂度是O（1）的，（有的会多一些，但有些也相应不会），所以总复杂度为O（max（m，n）），而预处理的复杂度为O（min（m，n））；
具体参考代码
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<cstdio>
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<<i+1-n<<endl,ans=true,j=next[j];
}
if(ans==false)
cout<<
"NO"<<endl;
return 0;
}
字典树
字典树，也称 Trie、字母树，指的是某个字符串集合对应的形如下图的有根树。一般树的每
条边上对应有恰好一个字符，每个顶点代表从根到该节点的路径所对应的字符串（将所有经
过的边上的字符按起来）
Trie树一般用于字符串的查找，匹配，能统计，排序，保存大量字符串信息，时间效率相当优秀（当然是以空间复杂度为代价的）
如果字符串为小写字母的话，字典树可以看成一个26叉树，而树的公共前缀可以很好的节省空间，插入和查询操作和树一样，一直往下走就了。
字典树主要的两种操作就是插入和查询，都是很简单的在树下走就是了
我们通过一个结构体来储存一个节点的信息：以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<bits/stdc++.h>
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<len;++i){
if(!tr[u].trans[s[i]-'a'])
tr[tr[u].trans[s[i]-'a']=++tot].init();
u=tr[u].trans[s[i]-'a'];
}
++tr[u].cnt;
}
void buildfail(){
static int qn,que[n*l];
que[qn=1]=1;
for(int ql=1;ql<=qn;++ql){
int u=que[ql],v,w;
for(int i=0;i<26;++i){
v=tr[u].fail;
while(!tr[v].trans[i]) v=tr[v].fail;
v=tr[v].trans[i],w=tr[u].trans[i];
if(w) {
tr[w].fail=v;que[++qn]=w;}
else tr[u].trans[i]=v;
}
}
}
int main(){
for(int i=0;i<26;i++) tr[0].trans[i]=1;
cin>>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<len;++i){
now=tr[now].trans[s[i]-'a'];
tmp=now;
while(tmp&&vst[tmp]!=tt){
vst[tmp]=tt;
ans+=tr[tmp].cnt;
tmp=tr[tmp].fail;
}
}
cout<<ans<<endl;
}
return 0;
}