P3808 【模板】AC自动机（简单版）

这是一道简单的AC自动机模板题。

用于检测正确性以及算法常数。

为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。

管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

输入样例#1： 复制

2
a
aa
aa

输出样例#1： 复制

2

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；

subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；

这个模板的原理是用字典树记录每个节点存在的单词数

通过kmp的指针一样的原理，跟模式串的每个单词进行匹配

最后加和得到ans

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 1000000+5
using namespace std;
struct Tree{
    int fail;
    int vis[26];
    int end;
}AC[maxn];
int cnt=0;
void Build(string s){
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++){
        if(AC[now].vis[s[i]-'a']==0)
            AC[now].vis[s[i]-'a']=++cnt;
        now=AC[now].vis[s[i]-'a'];
    }
    AC[now].end+=1;
}
void get_fail(){
    queue<int>Q;
    for(int i=0;i<26;i++){
        if(AC[0].vis[i]!=0){
            AC[AC[0].vis[i]].fail=0;
            Q.push(AC[0].vis[i]);
        }
    }
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=0;i<26;i++){
            if(AC[u].vis[i]!=0){
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                Q.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
        }
    }
}
int AC_query(string s){
    int l=s.length();
    int now=0,ans=0;
    for(int i=0;i<l;i++){
        now=AC[now].vis[s[i]-'a'];
        for(int t=now;t&&AC[t].end!=-1;AC[t].fail){
            ans+=AC[t].end;
            AC[t].end=-1;
        }
    }
    return ans;
}
int main(){
    int n;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        Build(s);
    }
    AC[0].fail=0;
    get_fail();
    cin>>s;
    cout<<AC_query(s)<<endl;
    //while(1)getchar();
    return 0;
}