【CUC集训】kmp+AC自动机题解

作者: 数字_ID | 来源:发表于2018-08-28 22:35 被阅读0次

【CUC集训】kmp+AC自动机题解
【CUC集训】字典树+kmp+字符串hash题解
AC自动机专题整理
字符串算法小结
程序设计语言|有限自动机
专业筛选
什么是自动机器学习？它有哪些用处？
编译器笔记6-词法分析-有穷自动机
了解Cucumber
约翰·冯·诺依曼

制作：邓楚盟
日期：2018年8月28日

A

AC自动机模板题，注意是统计包含哪些单词，不是统计总得出现次数

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Sd(x) scanf("%I64d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define gcd(a,b) __gcd((a),(b))
# define maxn 1000200
using namespace std;

const int max_tot = 500020;
struct Aho{

    int size = 1;
    queue<int>q;

    struct _node{
        int nxt[26];
        int cnt,fail;
    }node[max_tot];

    void init(){
        size = 1;
        while(!q.empty())q.pop();
        rep(i,max_tot){
            clr0(node[i].nxt);
            node[i].cnt = node[i].fail = 0;
        }
    }

    void ins(char *s){
        int n = strlen(s);
        int now = 0;
        rep(i,n){
            char c = s[i];
            if(!node[now].nxt[c-'a'])node[now].nxt[c-'a'] = size++;
            now = node[now].nxt[c-'a'];
        }
        node[now].cnt++;
    }

    void build(){
        node[0].fail = -1;
        q.push(0);
        W(!q.empty()){
            int u = q.front();
            q.pop();
            rep(i,26){
                if(node[u].nxt[i]){
                    if(u == 0)node[node[u].nxt[i]].fail = 0;
                    else{
                        int v = node[u].fail;
                        W(v!=-1){
                            if(node[v].nxt[i]){
                                node[node[u].nxt[i]].fail = node[v].nxt[i];
                                break;
                            }else{
                                v = node[v].fail;
                            }
                        }
                        if(v == -1)node[node[u].nxt[i]].fail = 0;
                    }
                    q.push(node[u].nxt[i]);
                }
            }
        }
    }

    int Get(int u){
        int res = 0;
        W(u){
            res += node[u].cnt;
            node[u].cnt = 0;
            u = node[u].fail;
        }
        return res;
    }
    int fid(char *s){
        int n = strlen(s);
        int res = 0;
        int now = 0;
        rep(i,n){
            char c = s[i];
            if(node[now].nxt[c-'a']){
                now = node[now].nxt[c - 'a'];
            }else{
                int p = node[now].fail;
                W(p!=-1&&node[p].nxt[c-'a'] == 0)p = node[p].fail;
                if(p == -1)now = 0;
                else now = node[p].nxt[c-'a'];
            }
            if(node[now].cnt){
                res += Get(now);
            }
        }
        return res;
    }

}aho;

char S[maxn];

int main()
{
    int T,N;
    Sc(T);
    W(T--){
        Sc(N);
        aho.init();
        rep(i,N){
            scanf("%s",S);
            aho.ins(S);
        }
        aho.build();
        scanf("%s",S);
        printf("%d\n",aho.fid(S));
    }
return 0;
}

B

典型的利用kmp的next数组求循环节的例题

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 1000020


using namespace std;


struct KMP{
    int nexta[maxn];
    void init(){
        clr0(nexta);
    }
    void getnext(char *s){
        clr0(nexta);
        nexta[0] = -1;
        int i = -1;int j = 0;
        int n = strlen(s);
        W(j<n){
            if(i == -1||s[i] == s[j]){
                nexta[j+1] = i+1;
                i++;j++;
            }else {
                i = nexta[i];
            }
        }
    }
    int kmp(char *s,char *t){
        int n = strlen(s);
        int m = strlen(t);
        int res = -1;
        int i = 0,j = 0;
        W(i<n&&j<m){
            if(j == -1||s[i] == t[j]){
                i++;j++;
            }else{
                j = nexta[j];
            }
        }
        if(j == m)res = i-m;
        return res;
    }
}kmp;

char s[maxn];
int main()
{
    int len;
    int Cs = 1;
    W(Sc(len)!=EOF){
        if(len == 0)break;
        kmp.init();
        clr0(s);
        scanf("%s",s);
        kmp.getnext(s);
        printf("Test case #%d\n",Cs++);
        repf(i,2,len){
            if(kmp.nexta[i] == -1||kmp.nexta[i] == 0)continue;
            int j = i-kmp.nexta[i];
            if(i%j == 0)printf("%d %d\n",i,i/j);
        }
        printf("\n");
    }
    return 0;
}

C

求一个串最长前缀使得和另一个串的最长后缀匹配
扩展kmp和kmp都能做

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define W(a) while(a)
# define Sc(x) scanf("%d",&(x))
# define Lson(x) (x)<<1
# define Rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 1000020


using namespace std;


struct KMP{
    int nexta[maxn];
    void init(){
        clr0(nexta);
    }
    void getnext(char *s){
        clr0(nexta);
        nexta[0] = -1;
        int i = -1;int j = 0;
        int n = strlen(s);
        W(j<n){
            if(i == -1||s[i] == s[j]){
                nexta[j+1] = i+1;
                i++;j++;
            }else {
                i = nexta[i];
            }
        }
    }
    int kmp(char *s,char *t){
        int n = strlen(s);
        int m = strlen(t);
        int res = -1;
        int i = 0,j = 0;
        W(i<n&&j<m){
            if(j == -1||s[i] == t[j]){
                i++;j++;
            }else{
                j = nexta[j];
            }
        }
        if(j == m)res = i-m;
        return res;
    }
}kmp;

char a[maxn*2];
char b[maxn];
int main()
{
    W(scanf("%s%s",a,b)!=EOF){
        kmp.init();
        int an = strlen(a);
        int bn = strlen(b);
        strcat(a,b);
        kmp.getnext(a);
        int ans = kmp.nexta[strlen(a)];
        W(ans>an||ans>bn)ans=kmp.nexta[ans];
        if(!ans)printf("0\n");
        else{
            a[ans] = 0;
            printf("%s %d\n",a,ans);
        }
    }
}

D

可以kmp+dp，也可以直接用扩展kmp做

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define ww(a) while(a)
# define sc(x) scanf("%d",&(x))
# define pc(x) printf("%d\n",(x));
# define lson(x) (x)<<1
# define rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 1000020


using namespace std;

const int mod = 1e4+7;

struct KMP{
    int nexta[maxn];
    void init(){
        clr0(nexta);
    }
    void getnext(char *s){
        clr0(nexta);
        nexta[0] = -1;
        int i = -1;int j = 0;
        int n = strlen(s);
        ww(j<n){
            if(i == -1||s[i] == s[j]){
                nexta[j+1] = i+1;
                i++;j++;
            }else {
                i = nexta[i];
            }
        }
    }
    int kmp(char *s,char *t){
        int n = strlen(s);
        int m = strlen(t);
        int res = -1;
        int i = 0,j = 0;
        ww(i<n&&j<m){
            if(j == -1||s[i] == t[j]){
                i++;j++;
            }else{
                j = nexta[j];
            }
        }
        if(j == m)res = i-m;
        return res;
    }
}kmp;

char a[maxn];
int dp[maxn];
int n;

int main()
{
    int T;sc(T);
    ww(T--){
        kmp.init();
        scanf("%d%s",&n,a);
        clr0(dp);
        kmp.getnext(a);
        int ans = 0;
        repf(i,1,n){
            dp[i] = (dp[kmp.nexta[i]]+1)%mod;
            ans = (ans+dp[i])%mod;
        }
        pc(ans);
    }
    return 0;
}

E

最大最小表示法例题，kmp求个循环节，除一下就好

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define ww(a) while(a)
# define sc(x) scanf("%d",&(x))
# define pc(x) printf("%d\n",(x));
# define lson(x) (x)<<1
# define rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 1000020


using namespace std;



struct KMP{
    int nexta[maxn];
    void init(){
        clr0(nexta);
    }
    void getnext(char *s){
        clr0(nexta);
        nexta[0] = -1;
        int i = -1;int j = 0;
        int n = strlen(s);
        ww(j<n){
            if(i == -1||s[i] == s[j]){
                nexta[j+1] = i+1;
                i++;j++;
            }else {
                i = nexta[i];
            }
        }
    }
    int kmp(char *s,char *t){
        int n = strlen(s);
        int m = strlen(t);
        int res = -1;
        int i = 0,j = 0;
        ww(i<n&&j<m){
            if(j == -1||s[i] == t[j]){
                i++;j++;
            }else{
                j = nexta[j];
            }
        }
        if(j == m)res = i-m;
        return res;
    }
}kmp;

int getmin(char *str){
    int i = 0, j = 1;
    int l;
    int len = strlen(str);
    while (i < len && j < len) {
        for (l = 0; l < len; l++)
            if (str[(i + l) % len] != str[(j + l) % len]) break;
        if (l >= len) break;
        if (str[(i + l) % len] > str[(j + l) % len]) i = i + l + 1;
        else j = j + l + 1;
        if (i == j) j++;
    }
    return i < j ? i : j;
}

int getmax(char *str){
    int i = 0, j = 1, k = 0;
    int len = strlen(str);
    while (i < len && j < len && k < len) {
        int t = str[(i + k) % len] - str[(j + k) % len];
        if (!t) k++;
        else {
            if (t > 0) j = j + k + 1;
            else i = i + k + 1;
            if (i == j) j++;
            k = 0;
        }
    }
    return i < j ? i : j;
}


int n;
char s[maxn];
int main()
{
    fuckio
    ww(scanf("%s",s)!=EOF){
        int len = strlen(s);
        kmp.init();
        kmp.getnext(s);
        int Min = getmin(s);
        int Max = getmax(s);
        int tmp = 0;
        if(len%(len-kmp.nexta[len]) == 0)tmp = len/(len-kmp.nexta[len]);
        else tmp =  1;
        printf("%d %d %d %d\n", Min + 1, tmp, Max + 1, tmp);
    }
}

F

原字符串x2，然后跑扩展kmp，枚举位置查看extnd数组，如果大于等于n说明，相等，否则比较不想等的那个位置的大小关系

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define ww(a) while(a)
# define sc(x) scanf("%d",&(x))
# define pc(x) printf("%d\n",(x));
# define lson(x) (x)<<1
# define rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 100020


using namespace std;

const int mod = 1e4+7;

struct KMP{
    int nexta[maxn];
    void init(){
        clr0(nexta);
    }
    void getnext(char *s){
        clr0(nexta);
        nexta[0] = -1;
        int i = -1;int j = 0;
        int n = strlen(s);
        ww(j<n){
            if(i == -1||s[i] == s[j]){
                nexta[j+1] = i+1;
                i++;j++;
            }else {
                i = nexta[i];
            }
        }
    }
    int kmp(char *s,char *t){
        int n = strlen(s);
        int m = strlen(t);
        int res = -1;
        int i = 0,j = 0;
        ww(i<n&&j<m){
            if(j == -1||s[i] == t[j]){
                i++;j++;
            }else{
                j = nexta[j];
            }
        }
        if(j == m)res = i-m;
        return res;
    }
}kmp;

struct EXKMP{
    int nexta[maxn];
    int extnd[maxn];
    void init(){
        clr0(nexta);
        clr0(extnd);
    }
    
    void getnxt(char *T)
    {
        init();
        int len=strlen(T),a=0;
        nexta[0]=len;
        while(a<len-1 && T[a]==T[a+1]) a++;
        nexta[1]=a;
        a=1;
        repf(k,2,len-1)
        {
            int p=a+nexta[a]-1,L=nexta[k-a];
            if( (k-1)+L >= p)
            {
                int j = (p-k+1)>0 ? (p-k+1) : 0;
                ww(k+j<len && T[k+j]==T[j]) j++;
                nexta[k]=j;
                a=k;
            }
            else
                nexta[k]=L;
        }
    }
    void getexnd(char *S,char *T)
    {
        getnxt(T);
        int slen=strlen(S),tlen=strlen(T),a=0;
        int MinLen = slen < tlen ? slen : tlen;
        while(a<MinLen && S[a]==T[a]) a++;
        extnd[0]=a;
        a=0;
        for(int k=1; k<slen; k++)
        {
            int p=a+extnd[a]-1, L=nexta[k-a];
            if( (k-1)+L >= p)
            {
                int j= (p-k+1) > 0 ? (p-k+1) : 0;
                while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
                extnd[k]=j;
                a=k;
            }
            else
                extnd[k]=L;
        }
    }
}ekmp;

char t[maxn];
char s[maxn*2];
int main()
{
    int T;sc(T);
    repf(tt,1,T){
        kmp.init();
        ekmp.init();
        scanf("%s",t);
        strcpy(s,t);
        strcat(s,t);
        ekmp.getexnd(s,t);
        kmp.getnext(t);
        int lens = strlen(s);
        int lent = strlen(t);
        int ans1 = 0,ans2 = 0,ans3 = 0;
        rep(i,lent){
            if(ekmp.extnd[i]>=lent)ans2++;
            else{
                if(s[i+ekmp.extnd[i]]<t[ekmp.extnd[i]]){
                    ans1++;
                }else{
                    ans3++;
                }
            }
        }
        int pr = 1;//循环节大小 
        if(lent%(lent-kmp.nexta[lent]) == 0){
            pr = lent/(lent-kmp.nexta[lent]);
        }
        printf ("Case %d: %d %d %d\n", tt, ans1 / pr, ans2 / pr, ans3 / pr);
    }
}

G

AC自动机板子题，会卡内存，建议使用指针形式写ac自动机（虽然我没有……）

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define ww(a) while(a)
# define sc(x) scanf("%d",&(x))
# define pc(x) printf("%d\n",(x));
# define lson(x) (x)<<1
# define rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 10020


using namespace std;

const int mod = 1e4+7;
const int max_tot = 60020;

vector<int>v;

struct Aho{

    int size = 1;
    queue<int>q;

    struct _node{
        int nxt[128];
        int cnt,fail,id;
    }node[max_tot];

    void init(){
        size = 1;
        while(!q.empty())q.pop();
        rep(i,max_tot){
            clr0(node[i].nxt);
            node[i].cnt = node[i].fail = node[i].id = 0;
        }
    }

    void ins(char *s,int x){
        int n = strlen(s);
        int now = 0;
        rep(i,n){
            char c = s[i];
            if(!node[now].nxt[c])node[now].nxt[c] = size++;
            now = node[now].nxt[c];
        }
        node[now].cnt++;
        node[now].id = x;
    }

    void build(){
        node[0].fail = -1;
        q.push(0);
        ww(!q.empty()){
            int u = q.front();
            q.pop();
            rep(i,128){
                if(node[u].nxt[i]){
                    if(u == 0)node[node[u].nxt[i]].fail = 0;
                    else{
                        int v = node[u].fail;
                        ww(v!=-1){
                            if(node[v].nxt[i]){
                                node[node[u].nxt[i]].fail = node[v].nxt[i];
                                break;
                            }else{
                                v = node[v].fail;
                            }
                        }
                        if(v == -1)node[node[u].nxt[i]].fail = 0;
                    }
                    q.push(node[u].nxt[i]);
                }
            }
        }
    }

    int fid(char *s){
        int n = strlen(s);
        bool res = false;
        int now = 0;
        rep(i,n){
            char c = s[i];
            if(node[now].nxt[c]){
                now = node[now].nxt[c];
            }else{
                int p = node[now].fail;
                ww(p!=-1&&node[p].nxt[c] == 0)p = node[p].fail;
                if(p == -1)now = 0;
                else now = node[p].nxt[c];
            }
            if(node[now].cnt){
                res = true;
                v.push_back(node[now].id);
            }
        }
        return res;
    }

}aho;

char s[maxn];
int n,m;
int main()
{
    fuckio
    ww(sc(n)!=EOF){
        aho.init();
        v.clear();
        rep(i,n){
            scanf("%s",s);
            aho.ins(s,i+1);
        }
        aho.build();
        sc(m);
        int tot = 0;
        repf(i,1,m){
            v.clear();
            scanf("%s",s);
            if(aho.fid(s)){
                tot ++;
                printf("web %d: ",i);
                sort(v.begin(),v.end());
                rep(i,v.size()-1)printf("%d ",v[i]);
                printf("%d\n",v[v.size()-1]);
            }
        }
        printf("total: %d\n",tot);
    }
return 0;
}

H

板子题
可以把A-Z以外的字符都归为第26号字符，A-Z是0-25

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit x&(-x)
# define ww(a) while(a)
# define sc(x) scanf("%d",&(x))
# define pc(x) printf("%d\n",(x));
# define lson(x) (x)<<1
# define rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 10020


using namespace std;

const int mod = 1e4+7;
const int max_tot = 50020;

vector<int>v;
int ans[1020];
struct Aho{

    int size = 1;
    queue<int>q;

    struct _node{
        int nxt[27];
        int cnt,fail,id;
    }node[max_tot];

    void init(){
        size = 1;
        while(!q.empty())q.pop();
        rep(i,max_tot){
            clr0(node[i].nxt);
            //rep(j,27)node[i].nxt[j] = 0;
            node[i].cnt = node[i].fail =node[i].id= 0;
        }
    }

    void ins(char *s,int x){
        int n = strlen(s);
        int now = 0;
        rep(i,n){
            int c = s[i]-'A';
            //if(c<0||c>25)c = 26;
            if(!node[now].nxt[c])node[now].nxt[c] = size++;
            now = node[now].nxt[c];
        }
        node[now].cnt++;
        node[now].id = x;
    }

    void build(){
        node[0].fail = -1;
        q.push(0);
        ww(!q.empty()){
            int u = q.front();
            q.pop();
            rep(i,27){
                if(node[u].nxt[i]){
                    if(u == 0)node[node[u].nxt[i]].fail = 0;
                    else{
                        int v = node[u].fail;
                        ww(v!=-1){
                            if(node[v].nxt[i]){
                                node[node[u].nxt[i]].fail = node[v].nxt[i];
                                break;
                            }else{
                                v = node[v].fail;
                            }
                        }
                        if(v == -1)node[node[u].nxt[i]].fail = 0;
                    }
                    q.push(node[u].nxt[i]);
                }
            }
        }
    }

    int fid(char *s){
        int n = strlen(s);
        int res = 0;
        int now = 0;
        rep(i,n){
            if(s[i]<'A'||s[i]>'Z')s[i]= 'Z'+1;
            int c = s[i]-'A';
            if(node[now].nxt[c]){
                now = node[now].nxt[c];
            }else{
                int p = node[now].fail;
                ww(p!=-1&&node[p].nxt[c] == 0)p = node[p].fail;
                if(p == -1)now = 0;
                else now = node[p].nxt[c];
            }
            if(node[now].cnt){
                res++;
                ans[node[now].id]++;
            }
        }
        return res;
    }

}aho;

char virus[1020][100];
char s[2000020];
int n,m;
int main()
{
    ww(sc(n)!=EOF){
        clr0(ans);
        aho.init();
        repf(i,1,n){
            scanf("%s",virus[i]);
            aho.ins(virus[i],i);
        }
        aho.build();
        scanf("%s",s);
        if(aho.fid(s)){
            repf(i,1,n){
                if(ans[i]){
                    printf("%s: %d\n",virus[i],ans[i]);
                }
            }
        }
    }
return 0;
}

【CUC集训】kmp+AC自动机题解
制作：邓楚盟日期：2018年8月28日 A AC自动机模板题，注意是统计包含哪些单词，不是统计总得出现次数 B ...
【CUC集训】字典树+kmp+字符串hash题解
制作：数字_ID 日期：2018年8月27日 A (HDU - 2087) 简单KMP，注意匹配成功之后j归0 B...
AC自动机专题整理
AC自动机学习记录参考资料字典树（讲解+模版）AC自动机算法AC自动机算法详解hdu 2222 ac自动机入门...
字符串算法小结
hash kmp和ac自动机后缀数组，后缀自动机，后缀树扩展kmp manacher算法回文自动机可删改的...
程序设计语言|有限自动机
有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机有两类：确定的有限自动机和不确定的有限自动机。...
专业筛选
【学术硕士】信息传播学——口述历史 http://yz.cuc.edu.cn/downloadWYFHY/zyf...
什么是自动机器学习？它有哪些用处？
一、认识自动机器学习 1、自动机器学习的概念：自动机器学习（AutoML）旨在通过让一些通用步骤 (如数据预处...
编译器笔记6-词法分析-有穷自动机
一有穷自动机 (Finite Automata) 简介有穷自动机(Finite Automata，FA)由两位...
了解Cucumber
本文主要介绍cucumber-jvm的使用。什么是Cucumber？ Cucumber能做什么？如何使用Cuc...
约翰·冯·诺依曼
细胞自动机