【テンプレート】AC自動機(補強版)洛谷3796 AC自動機

タイトル
NN個の小文字からなるパターン列とテキスト列TTがある.各パターン列は、テキスト列に複数回表示される場合があります.テキスト列TTに最も多く現れるパターン列を見つける必要があります.
ぶんせき
改める
code

#include
#include
#include
#include
#include
#include
#include

using namespace std;

struct Tree{
    int fail,from;
    int vis[26];
    int num;
}ac[1000000];
int n;
int cnt=0;

int w[1000000];
string ss[500];

void Build(string s,int x)
{
    int l=s.length();
    int now=0;
    for(int i=0;iif(ac[now].vis[s[i]-'a']==0) ac[now].vis[s[i]-'a']=++cnt;
        now=ac[now].vis[s[i]-'a'];
    }
    ac[now].num+=1; 
    ac[now].from=x;
}

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];
        }
    }
}

void ac_Query(string s)
{
    int l=s.length();
    int now=0,ans=0;
    for(int i=0;i'a'];
        for(int t=now;t&&(ac[t].num!=-1);t=ac[t].fail)
        {
            if (ac[t].from!=0) w[ac[t].from]++;
            //ac[t].num=-1;
        } 
    }
    for (int i=1;i<=n;i++)
    {
        if (w[i]>ans) ans=w[i];
    }
    printf("%d
",ans);
    for (int i=1;i<=n;i++)
    {
        if (w[i]==ans) cout<int main()
{
    scanf("%d",&n);
    while (n){
    memset(ac,0,sizeof(ac));
    memset(w,0,sizeof(w));
    cnt=0;
    w[0]=0;
    for(int i=1;i<=n;++i)
    {
        string s;
        cin>>s;
        ss[i]=s;
        Build(s,i);
    }
    ac[0].fail=0;
    Get_fail();
    string s;
    cin>>s;
    ac_Query(s);
    scanf("%d",&n);
    }
}