1 条题解

  • 0
    @ 2025-10-8 16:51:11
    #include <bits/stdc++.h>
    using namespace std;
    const int N=155;
    char str[N][80], T[1110000];
    int ch[N*70][26], id, ed[N*70], pre[N*70], num[N];
    void ins(char *s, int x)
    {
        int p=0;
        for(int i=0;s[i];i++)
        {
            int j=s[i]-'a';
            if(ch[p][j]==0) ch[p][j]=++id;
            p=ch[p][j];
        }
        ed[p]=x;
    }
    void build()
    {
        queue<int> Q;
        for(int i=0;i<26;i++)if(ch[0][i])Q.push(ch[0][i]);
        while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            for(int i=0;i<26;i++)
            {
                int &y=ch[x][i];
                if(y==0)     y=ch[pre[x]][i];
                else    pre[y]=ch[pre[x]][i], Q.push(y);
            }
        }
    }
    void query(char *s)
    {
        int p=0;
        for(int i=0;s[i];i++)
        {
            p=ch[p][s[i]-'a'];
            for(int j=p;j;j=pre[j])
                num[ed[j]]++;
        }
    }
    int main()
    {
        int n;
        while(scanf("%d", &n)!=EOF && n)
        {
            id=0;memset(ch,0,sizeof(ch));memset(ed,0,sizeof(ed)); 
            for(int i=1;i<=n; i++)scanf("%s", str[i]), ins(str[i],i);
            memset(pre,0,sizeof(pre));build();
             
            scanf("%s", T);
            memset(num,0,sizeof num);
            query(T);
            int mx=0;for(int i=1;i<=n;i++) mx=max(mx,num[i]);
            printf("%d\n", mx);
            for(int i=1;i<=n;i++) if(num[i]==mx) printf("%s\n", str[i]);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    512
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    187
    已通过
    34
    上传者