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

#include 
     
      const int maxn = 3*1e6+5, M = 1e6+7;using namespace std;int siz, cur[maxn];bool flag[maxn];struct ac{    struct Sta{        int son[26], fail;        int cnt, rr;    }sta[maxn];    void init(){        siz = 1;    }    void insert(char *S, int tot){        int len = strlen(S);        int now = 0;        for(int i = 0; i < len; i++){            char c = S[i];            if(sta[now].son[c-'a'] == 0)                sta[now].son[c-'a'] = siz++;            now = sta[now].son[c-'a'];        }        sta[now].cnt++;    };    void build(){        queue 
      
        Q;        Q.push(0);        while(!Q.empty()){            int u = Q.front(); Q.pop();            for(int i = 0; i < 26; i++){                if(sta[u].son[i]){                    if(u == 0)sta[sta[u].son[i]].fail = 0;                    else                         sta[sta[u].son[i]].fail = sta[sta[u].fail].son[i];                     Q.push(sta[u].son[i]);                }                else sta[u].son[i] = sta[sta[u].fail].son[i];            }        }    }    int match(char *S){        int now = 0, res = 0;        int len = strlen(S);        for(int i = 0; i < len; i++){            char c = S[i];            now = sta[now].son[c - 'a'];            for(int t = now; t && !flag[t]; t = sta[t].fail)                res += sta[t].cnt, flag[t] = 1;        }        return res;    }    int Query(int t){        return sta[cur[t]].rr;    }}Tr;char a[maxn][55];char s[M];char S[M];int main(){    int n ,m;    scanf("%d", &n);    Tr.init();    for(int i = 1; i <= n; i++){       // scanf("\n");        scanf("%s", s);        Tr.insert(s, i);    }    Tr.build();   // scanf("\n");    scanf("%s", S);    printf("%d\n", Tr.match(S));    return 0;}
      
     

有 NN 个由小写字母组成的模式串以及一个文本串 TT 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 TT 中出现的次数最多。

#include 
     
      const int maxn = 3*1e6+5, M = 1e6+7;using namespace std;int siz;bool flag[maxn];struct Result{    int sum , id;}ans[M];struct ac{    struct Sta{        int son[26], fail;        int end, rr;    }sta[maxn];    void clear(int x){        memset(sta[x].son, 0, sizeof(sta[x].son));        sta[x].end = sta[x].fail = 0;    }    void insert(char *S, int tot){        int len = strlen(S);        int now = 0;        for(int i = 0; i < len; i++){            char c = S[i];            if(sta[now].son[c-'a'] == 0){                sta[now].son[c-'a'] = ++siz;                clear(siz);            }                now = sta[now].son[c-'a'];         }        sta[now].end = tot;    };    void build(){        queue 
      
        Q;        Q.push(0);        while(!Q.empty()){            int u = Q.front(); Q.pop();            for(int i = 0; i < 26; i++){                if(sta[u].son[i]){                    if(u == 0)sta[sta[u].son[i]].fail = 0;                    else                         sta[sta[u].son[i]].fail = sta[sta[u].fail].son[i];                     Q.push(sta[u].son[i]);                }                else sta[u].son[i] = sta[sta[u].fail].son[i];            }        }    }    void match(char *S){        int now = 0, res = 0;        int len = strlen(S);        for(int i = 0; i < len; i++){            char c = S[i];            now = sta[now].son[c - 'a'];            for(int t = now; t; t = sta[t].fail)                ans[sta[t].end].sum++;        }    }}Tr;char a[M][75];char S[M];bool cmp(Result a, Result b){    return a.sum == b.sum ? a.id < b.id : a.sum > b.sum;}int main(){    int n ,m;    while(scanf("%d", &n) == 1){        if(!n)break;        siz = 0;        for(int i = 1; i <= n; i++){            ans[i].id = i;            ans[i].sum = 0;        }        Tr.clear(0);        for(int i = 1; i <= n; i++){            scanf("%s", a[i]);            Tr.insert(a[i], i);        }        Tr.build();        scanf("%s", S);        Tr.match(S);        sort(ans+1, ans+1+n, cmp);        printf("%d\n", ans[1].sum);        for(int i = 1; i <= n; i++){            if(ans[i].sum < ans[1].sum)break;            printf("%s\n", a[ans[i].id]);        }        }        return 0;}