模板——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]，所以不用担心从前往后枚举文本串的前缀会过长。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int inf=(int)(2e9);

 const ll INF=(ll)(5e18);

 const int N=;

 //nxt:保存最长的后缀字串

 char s[N];

 int nxt[N],n,ch[N][],cnt=;

 int bl[N],ans=;

 void make(char *s)

 {

     int len=strlen(s),u=;

     for(int i=;i<len;i++)

     {

         int c=s[i]-'a';

         if(!ch[u][c]) ch[u][c]=++cnt;

         u=ch[u][c];

     }

     bl[u]++;//不能只赋值为1，可能有完全相同的字符串

 }

 void bfs()

 {

     for(int i=;i<;i++) ch[][i]=;

     queue<int> q;

     q.push(); nxt[]=;

     while(!q.empty())

     {

         int u=q.front(); q.pop();

         for(int i=;i<;i++)

         {

             if(!ch[u][i]) ch[u][i]=ch[nxt[u]][i];//剪枝

             else

             {

                 int v=ch[u][i];

                 nxt[v]=ch[nxt[u]][i];

                 q.push(v);

             }

         }

     }

 }

 void query(char *s)

 {

     int len=strlen(s),u=;

     for(int i=;i<len;i++)

     {

         int c=s[i]-'a';

         int k=ch[u][c];

         while(k>&&bl[k]!=-)

         {

             ans+=bl[k];

             bl[k]=-;//剪枝

             k=nxt[k];

         }

         u=ch[u][c];

     }

     printf("%d\n",ans);

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%s",s);

         make(s);

     }

     bfs();

     scanf("%s",&s);

     query(s);

     return ;

 }

巴特西

模板——AC自动机

最新文章

热门文章