# KMP 模板和 AC 自动机模板

# KMP 模板

int fail[N];

char mot[N],son[N];

void pre()//预处理子串 
{
    fail[0]=-1;
    for(int i=1;i<son_len;i++)
    {
        int pos=fail[i-1];
        while(pos!=-1 && son[pos]!=son[i-1])
            pos=fail[pos];
        fail[i]=++pos;
    }
    return;
}

int KMP()
{
    int ans=0,i=0,j=0;
    while(i<mot_len)
    {
        while(j>=0 && son[j]!=mot[i])
            j=fail[j];
        j++;
        if(j==mot_len)
            ans++,j=fail[j-1];
        else
            i++;
    }
    return ans;
}

例题：KMP 模板题

# KMP 模板题解:

#include <bits/stdc++.h>
using namespace std;
const int N=1000001;

char son[N],mot[N];
vector <int > ans;
int fail[N],T;

void pre(int len)
{
	fail[0]=-1;
	for(int i=1;i<len;i++)
	{
		int pos=fail[i-1];
		while(pos!=-1 && son[pos]!=son[i-1])
			pos=fail[pos];
		fail[i]=++pos;
	}
	return;
}

void kmp(int mot_len,int son_len)
{
	int i=0,j=0;
	while(i<mot_len)
	{
		while(j>=0 && son[j]!=mot[i]) 
			j=fail[j];
		j++;
		if(j==son_len) 
			ans.push_back(i-j+1),j=fail[j-1];
		else
			i++;
	}
	return;
}

int main()
{
	scanf("%s %s",mot,son);
	int mot_len=strlen(mot);
	int son_len=strlen(son);
	pre(mot_len);
	kmp(mot_len,son_len);
	int size=ans.size();
	for(int i=0;i<size;i++)
		printf("%d\n",ans[i]+1);
	for(int i=1;i<=son_len;i++)
		printf("%d ",fail[i]);
	return 0;
}

例题：AC 自动机模板

# AC 自动机模板题解：

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
const int N=1000001;
int tree[N][27],T,n,tot,beh[N];
string s;
int finish[N];
queue <int > q;
void init()
{
    while(!q.empty())
        q.pop();
    memset(tree,0,sizeof(tree));
    memset(beh,0,sizeof(beh));
    memset(finish,0,sizeof(finish));
    return;
}
void build(string s,int len)
{
    int root=0;
    for(int i=0; i<len; i++)
    {
        int t=s[i]-'a';
        if(tree[root][t]==0)
        {
            tree[root][t]=++tot;
            memset(tree[tot],0,sizeof(tree[tot]));
        }
        root=tree[root][t];
    }
    finish[root]++;
    return;
}
void bfs()
{
    for(int i=0; i<26; i++)
    {
        if(tree[0][i]!=0)
        {
            beh[tree[0][i]]=0;
            q.push(tree[0][i]);
        }
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0; i<26; i++)
        {
            if(tree[t][i]==0)
                tree[t][i]=tree[beh[t]][i];
            else
            {
                beh[tree[t][i]]=tree[beh[t]][i];
                q.push(tree[t][i]);
            }
        }
    }
    return;
}
int query(string s,int len)
{
    int ans=0,root=0;
    for(int i=0; i<len; i++)
    {
        int t=s[i]-'a';
        root=tree[root][t];
        for(int j=root; j!=0 && finish[j]!=-1; j=beh[j])
            ans+=finish[j],finish[j]=-1;
    }
    return ans;
}
int main()
{
        cin>>n;
        string t;
        for(int i=1; i<=n; i++)
        {
            cin>>t;
            build(t,t.length());
        }
        cin>>s;
        bfs();
        cout<<query(s,s.length())<<endl;
    return 0;
}