#11WA求调
查看原帖
#11WA求调
1092451
DigitalSerenade楼主2025/8/4 16:14
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
namespace AC{
    struct node{
        int son[26];
        int fail;
        int cnt;
        int occur;

        void init(){
            memset(son,0,sizeof(son));
            occur=fail=cnt=0;
        }
    }trie[N];
    int tot;
    vector<int>endpos;
    vector<string>patten;

    void Init(){
        tot=0;
        trie[0].init();
        patten.clear();
        endpos.clear();
    }

    void insert(string s){
        int u=0;
        for(char c:s){
            int& son=trie[u].son[c-'a'];
            if(!son){
                son=++tot;
                trie[son].init();
            }
            u=son;
        }
        trie[u].cnt++;
        patten.push_back(s);
        endpos.push_back(u);
    }

    void build(){
        for(auto& i:trie)i.occur=0;

        queue<int>q;
        for(int i=0;i<26;i++){
            if(trie[0].son[i])q.push(trie[0].son[i]);
        }

        while(!q.empty()){
            int u=q.front();
            q.pop();

            for(int i=0;i<26;i++){
                if(trie[u].son[i]){
                    trie[trie[u].son[i]].fail=trie[trie[u].fail].son[i];
                    q.push(trie[u].son[i]);
                }
                else trie[u].son[i]=trie[trie[u].fail].son[i];
            }
        }
    }

    vector<int> query(string t){
        vector<int>ans;
        int u=0,res=0;
        for(char& c:t){
            u=trie[u].son[c-'a'];
            trie[u].occur++;
        }

        for(int i=tot;i;i--){
            int f=trie[i].fail;
            trie[f].occur+=trie[i].occur;
        }

        for(auto& u :endpos) ans.push_back(trie[u].occur);
        return ans;
    }
}

int main(){
    int n;
    vector<int>ans;
    while(true){
        ans.clear();
        cin>>n;
        if(!n) break;
        AC::Init();
        while(n--){
            string s;
            cin>>s;
            AC::insert(s);
        }
        AC::build();
        string t;
        cin>>t;
        ans=AC::query(t);
        int maxnum=*max_element(ans.begin(),ans.end());
        cout<<maxnum<<'\n';
        for(int i=0;i<ans.size();i++){
            if(ans[i]==maxnum){
                cout<<AC::patten[i]<<'\n';
            }
        }
    }
}
2025/8/4 16:14
加载中...