模板——AC自动机

传送门:QAQQAQ

 

定义nxt[u]=v表示从u开始不断沿着失配边跳到的第一个是标记点的端点v,那么我们再匹配时沿着last跳,每跳到一个last,它就一定对应一个模式串,所以效率是非常高的。

和KMP一样,我们只需检测ch[u][c]和ch[nxt[u]][c]的下一个字符是否相同,即可进行nxt数组的初始化,即:

从0~25枚举c,令v=ch[u][c]

则nxt[v]=ch[nxt[u]][c]。

这个nxt[v]并不能保证ch[u][c]就一定存在,所以还需要一个while循环一直跳直到找到一个ch[u][c]!=0的端点。出现了一个while,既使代码不够优美,又使效率无法保证.

所以我们直接把所有ch[k][c]=0的端点的ch[k][c]直接连向ch[nxt[k]][c],就好像并差集的一个路径压缩,由于Trie是读完所有模式串后建的,所以这个加边并不会影响Trie,这样就不用担心节点是否存在的问题了(无论如何都会在根节点1上停止,我们先创建一个虚拟节点0,把0的26条边都连在1上,令nxt[1]=0,那么后面无论情况再糟最后也只是nxt[x]=1)。

考虑到这是一个Trie树上的递推,所以我们用BFS搞一搞就好了。

 

在查询时,只需对于当前字符串不停跳nxt,判断是否是模式串的结尾即可,因为ch[k][c]=0的端点的ch[k][c]直接连向ch[nxt[k]][c],所以不用担心从前往后枚举文本串的前缀会过长。

模板——AC自动机
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int inf=(int)(2e9);
 5 const ll INF=(ll)(5e18);
 6 const int N=1000010;
 7 
 8 //nxt:保存最长的后缀字串 
 9 char s[N];
10 int nxt[N],n,ch[N][26],cnt=1;
11 int bl[N],ans=0;
12 
13 void make(char *s)
14 {
15     int len=strlen(s),u=1;
16     for(int i=0;i<len;i++)
17     {
18         int c=s[i]-'a';
19         if(!ch[u][c]) ch[u][c]=++cnt;
20         u=ch[u][c];
21     }
22     bl[u]++;//不能只赋值为1,可能有完全相同的字符串 
23 }
24 
25 void bfs()
26 {
27     for(int i=0;i<26;i++) ch[0][i]=1;
28     queue<int> q; 
29     q.push(1); nxt[1]=0;
30     while(!q.empty())
31     {
32         int u=q.front(); q.pop();
33         for(int i=0;i<26;i++)
34         {
35             if(!ch[u][i]) ch[u][i]=ch[nxt[u]][i];//剪枝 
36             else
37             {
38                 int v=ch[u][i];
39                 nxt[v]=ch[nxt[u]][i];
40                 q.push(v);
41             }
42         }
43     }
44 }
45 
46 void query(char *s)
47 {
48     int len=strlen(s),u=1;
49     for(int i=0;i<len;i++)
50     {
51         int c=s[i]-'a';
52         int k=ch[u][c];
53         while(k>1&&bl[k]!=-1)
54         {
55             ans+=bl[k];
56             bl[k]=-1;//剪枝 
57             k=nxt[k];
58         }
59         u=ch[u][c];
60     }
61     printf("%d\n",ans);
62 }
63 
64 int main()
65 {
66     scanf("%d",&n);
67     for(int i=1;i<=n;i++)
68     {
69         scanf("%s",s);
70         make(s);
71     } 
72     bfs();
73     scanf("%s",&s);
74     query(s);
75     return 0;
76 }
View Code

 

上一篇:P3008 [USACO11JAN]道路和飞机Roads and Planes


下一篇:利用Xtrabackup进行单库备份、单表恢复实例