复杂度：

查找O(n)，维护O(n)

概要：

应用了kmp的自匹配思想，在trie建图时维护一个fali指针，指向上一个匹配的点，这点是用bfs做到。匹配串的时候同样没匹配到就和kmp一样返回。

应用：单串匹配多模板，维护多模板里边的信息。

技巧及注意：

插入和trie一样，然后是bfs。

在bfs的过程中，注意以根开头的不需要匹配fail，即ch[0][i]不需要匹配他们的fail，即为空。

然后在查找的时候当找到一个时我们要遍历这个节点的整个fail树，然后取出信息后记得将信息清空。

一定要注意！节点数是不超过n个串的总长度！！！一定要切记！！！

注意！！bfs的时候一定要维护信息！！！！

例题：

1. （将自动机的节点作为转移的状态然后递推）

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a
           
          
         
        
       
      
     

 

 

---

 

 

没错，就是AC自动机！（可惜不像金坷垃那样～）

不多说，放上模板，不难理解的。

#include 
     
      #include 
      
       #include 
       
        #define for1(i,a,n) for(i=a;i<=n;++i)#define for2(i,a,n) for(i=a;i
        
         =a;--i)#define for4(i,a,n) for(i=n;i>a;--i)#define CC(i,a) memset(i, a, sizeof(i))using namespace std;const int N=10000000, Type=26;char a[N], b[N];int ch[N][Type], fail[N], w[N], ans, cnt=1;queue
         
           q;void ins(char* s) {	int u=0, v, i, len=strlen(s);	for2(i, 0, len) {		v=s[i]-'a';		if(!ch[u][v]) ch[u][v]=cnt++;		u=ch[u][v];	}	w[u]++;}void bfs() {	fail[0]=0;	q.push(0);	int u, p, i;	while(!q.empty()) {		u=q.front(); q.pop();		for2(i, 0, Type) if(ch[u][i]) {			q.push(ch[u][i]); //先插入，后判断			if(!u) continue; //不要在这里错了。。			p=fail[u];			while(p && !ch[p][i]) p=fail[p];			fail[ch[u][i]]=ch[p][i];		}	}}void ac(char* s) {	int i, u=0, v, len=strlen(s), t;	for2(i, 0, len) {		v=s[i]-'a';		while(u && !ch[u][v]) u=fail[u];		u=ch[u][v];		t=u;		while(t) {			ans+=w[t];			w[t]=0;			t=fail[t];		}	}}void init() {	CC(fail, 0);	CC(ch, 0);	CC(w, 0);}int main() {	init();	scanf("%s", a);	int n, i;	scanf("%d", &n);	for1(i, 1, n) {		scanf("%s", b);		ins(b);	}	bfs();	ac(a);	printf("%d\n", ans);		return 0;}
         
        
       
      
     

 注意一些细节即可