AC自动机

这些东西还是交给wiki

模板

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
string s[1000001];
int fail[1000001];
int cnt;
int x;
int ed[1000001];
queue<int> q;
int tr[1000001][26];
void add(string s){
    int l=s.length();
    int p=0;
    for(int i=0;i<l;++i){
        x=s[i]-'a';
        if(!tr[p][x]){
            tr[p][x]=++cnt;
        }
        p=tr[p][x];
    }
    ed[p]++;
}
void build(){
    for(int i=0;i<26;++i){
        if(tr[0][i]){
            fail[tr[0][i]]=0;
            q.push(tr[0][i]);
        }
    }
    while(!q.empty()){
        x=q.front();
        q.pop();
        for(int i=0;i<26;++i){
            if(tr[x][i]){
                fail[tr[x][i]]=tr[fail[x]][i];
                q.push(tr[x][i]);
            }else{
                tr[x][i]=tr[fail[x]][i];
            }
        }
    }
}
string ques;
int que(string s){
    int l=s.length();
    int p=0;
    int ans=0;
    for(int i=0;i<l;++i){
        x=s[i]-'a';
        p=tr[p][x];
        for(int j=p;j&&ed[j]!=-1;j=fail[j]){
            ans+=ed[j];
            ed[j]=-1;
        }
    }
    return ans;
}
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        cin>>s[i];
        add(s[i]);
    }
    build();
    cin>>ques;
    cout<<que(ques);
    return 0;
}

然后加强版来了

改一改然后暴力卡常？那太无聊了

可以注意到我们更新答案的时候是依据者fail来更新的，并且fail构成了一颗树

那么为什么不能从深度深向浅更新呢？

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
string s[1001];
int fail[205001];
int cnt;
int x;
int ed[201501];
queue<int> q;
int deep[201501];
vector<int> dep[101];
int tr[205001][27];
int pl[2001];
int add(string s){
    int l=s.length();
    int p=0;
    for(int i=0;i<l;++i){
        x=s[i]-'a';
        if(!tr[p][x]){
            tr[p][x]=++cnt;
            deep[tr[p][x]]=deep[p]+1;
            dep[deep[p]+1].push_back(tr[p][x]);
        }
        p=tr[p][x];
    }
    ed[p]++;
    return p;
}
void build(){
    for(int i=0;i<26;++i){
        if(tr[0][i]){
            fail[tr[0][i]]=0;
            q.push(tr[0][i]);
        }
    }
    while(!q.empty()){
        x=q.front();
        q.pop();
        for(int i=0;i<26;++i){
            if(tr[x][i]){
                fail[tr[x][i]]=tr[fail[x]][i];
                q.push(tr[x][i]);
            }else{
                tr[x][i]=tr[fail[x]][i];
            }
        }
    }
}
string ques;
int got[1500001];
int que(string s){
    int l=s.length();
    int p=0;
    int ans=0;
    for(int i=0;i<l;++i){
        x=s[i]-'a';   
        p=tr[p][x];
        got[p]++;
    }
    for(int i=72;i>0;--i){
        for(int j=0;j<(int)dep[i].size();++j){
            int x=dep[i][j];
            got[fail[x]]+=got[x];
        }
    }
    for(int i=1;i<=cnt;++i){
        if(ed[i]) ans=max(ans,got[i]);
    }
    return ans;
}
int t;
int main(){
    while(1){
    read(n);
    if(n==0) return 0;
    for(int i=1;i<72;++i){
        dep[i].clear();
    }
    memset(got,0,sizeof(got));
    memset(tr,0,sizeof(tr));
    memset(ed,0,sizeof(ed));
    memset(deep,0,sizeof(deep));
    memset(fail,0,sizeof(fail));
    memset(pl,0,sizeof(pl));
    cnt=0;
    for(int i=1;i<=n;++i){
        cin>>s[i];
        pl[i]=add(s[i]);
    }
    build();
    cin>>ques;
    int ans=que(ques);
    cout<<ans<<endl;
    for(int i=1;i<=n;++i){
        if(got[pl[i]]==ans){
            cout<<s[i]<<endl;
        }
        }
    }
    return 0;
}