第1个点WA了,求调
查看原帖
第1个点WA了,求调
362878
jerry090811楼主2022/6/5 22:06
#include <bits/stdc++.h>
using namespace std;
int c[15010];
string a[15000];
struct node
{
    int son[26];
    int fail;
    bool is_end;
    int ends;
}p[15010];
int cnt=0;
void trie(string x,int k)
{
    int n=x.size();
    int pos=0;
    for (int i=0;i<n;i++){
        if (p[pos].son[x[i]-'a']==0){
            p[pos].son[x[i]-'a']=++cnt;
        }
        pos=p[pos].son[x[i]-'a'];
    }
    p[pos].is_end=true;
    p[pos].ends=k;
}
void build()
{
    queue<int> q;
    p[0].fail=0;
    for (int ch=0;ch<26;ch++){
        if (p[0].son[ch]) {p[p[0].son[ch]].fail=0;q.push(p[0].son[ch]);}
    }
    while (!q.empty()){
        int x=q.front();
        q.pop();
        for (int ch=0;ch<26;ch++){
            if (p[x].son[ch]){
                p[p[x].son[ch]].fail=p[p[x].fail].son[ch];
                q.push(p[x].son[ch]);
            }
            else{
                p[x].son[ch]=p[p[x].fail].son[ch];
            }
        }
    }
}
void scan(string x)
{
    int pos=0;
    int n=x.size();
    for (int i=0;i<n;i++){
        pos=p[pos].son[x[i]-'a'];
        if (p[pos].is_end==false) continue;
        for (int j=pos;j;j=p[j].fail){
            if (p[j].is_end==true) c[p[j].ends]++;
        }
    }
}
void init()
{
    memset(p,0,sizeof(p));
    memset(c,0,sizeof(c));
    memset(a,0,sizeof(a));
    cnt=0;
}
int main()
{
    int n;
    while (1){
        init();
        cin>>n;
        if (n==0) return 0;
        for (int i=0;i<n;i++){
            string x;
            cin>>x;
            a[i]=x;
            trie(x,i);
        }
        build();
        string t;
        cin>>t;
        scan(t);
        int maxn=0;
        for (int i=0;i<n;i++){
            if (c[i]>maxn) maxn=c[i];
        }
        cout<<maxn<<endl;
        for (int i=0;i<n;i++){
            if (c[i]==maxn) cout<<a[i]<<endl;
        }
    }
    return 0;
}
/*
10
qabqks
vimbirqy
cflwvxtp
klljfj
ab
nkeiid
fkypjfev
yvgp
evdhs
xaizql
qabqksatffqpjomzstjabfklljfjqevdhsqabqkscflwvxtpeevdhsmzonkeiid
*/


代码很丑,求轻喷。

后边附上了错误的样例,答案是3 ab,我输出的是2 qabqks evdhs

实在调不动了,求调

2022/6/5 22:06
加载中...