[JSOI2007] 文本生成器 - AC自动机,dp

// Which pattern string occurred for the most times
#include <bits/stdc++.h>
using namespace std;
struct ACA {
    queue <int> q;
    int c[500005][26],val[500005],fi[500005],cnt,ans[1005];
    vector <int> g[500005];
    void init() {
        memset(c,0,sizeof c);
        memset(val,0,sizeof val);
        memset(fi,0,sizeof fi);
        memset(ans,0,sizeof ans);
        cnt=0;
    }
    void ins(char *str,int id) {
        int len=strlen(str), p=0;
        for(int i=0; i<len; i++) {
            int v=str[i]-'A';
            if(!c[p][v]) c[p][v]=++cnt;
            p=c[p][v];
        }
        val[p]=id;
    }
    void dfs(int p) {
        for(int i=0;i<g[p].size();i++) {
            val[g[p][i]]|=val[p];
            dfs(g[p][i]);
        }
    }
    void build() {
        for(int i=0; i<26; i++) if(c[0][i]) fi[c[0][i]]=0, q.push(c[0][i]);
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            for(int i=0; i<26; i++)
                if(c[u][i]) fi[c[u][i]]=c[fi[u]][i], q.push(c[u][i]);
                else c[u][i]=c[fi[u]][i];
        }
        for(int i=0;i<=cnt;i++) if(fi[i]!=i) g[fi[i]].push_back(i);
        dfs(0);
    }
} AC;
int n,m;
char p[1000005];
string mp[1005];
int f[105][10005];
int main() {
    cin>>n>>m;
    memset(p,0,sizeof p);
    AC.init();
    for(int i=1; i<=n; i++) scanf("%s",p), AC.ins(p,i), mp[i]=p;
    AC.build();
    f[0][0]=1;
    for(int i=0;i<26;i++) {
        if(AC.val[AC.c[0][i]]==0) (f[1][AC.c[0][i]]+=f[0][0])%=10007;
    }
    for(int i=1;i<=m;i++) {
        for(int j=0;j<=AC.cnt;j++) {
            for(int k=0;k<26;k++) {
                if(AC.val[AC.c[j][k]]==0)
                    (f[i+1][AC.c[j][k]]+=f[i][j])%=10007;
            }
        }
    }
    int ans = 0;
    for(int i=0;i<=AC.cnt;i++)
        (ans+=f[m][i])%=10007;
    int tot = 1;
    for(int i=1;i<=m;i++) (tot*=26)%=10007;
    cout<<(10007+tot-ans)%10007<<endl;
}

[JSOI2007] 文本生成器 - AC自动机,dp

原文：https://www.cnblogs.com/mollnn/p/12254705.html