本地运行结果与洛谷评测机运行结果不一致。。。在洛谷评测机上我的代码第一个数字全部输出了0,但本地运行答案似乎是正确的???
#include <bits/stdc++.h>
using namespace std;
const int MAXN=155, MAXL=11005;
int N;
struct AC{
string s[MAXN];
int trie[MAXL][30], num[MAXL], fail[MAXL], ans[MAXN], node, N;
AC(){
for(int i=0; i<MAXL; i++){
num[i]=fail[i]=0;
for(int j=1; j<=26; j++){
trie[i][j]=0;
}
}
for(int i=1; i<MAXN; i++){
ans[i]=0;
}
}
void insert(string str, int ord){
int key=0;
for(int i=0; i<str.length(); i++){
if(!trie[key][str[i]-96]){
node++;
trie[key][str[i]-96]=node;
}
key=trie[key][str[i]-96];
}
num[key]=ord;
}
void build(){
for(int i=1; i<=N; i++){
insert(s[i], i);
}
queue<int> q;
for(int i=1; i<=26; i++){
if(trie[0][i]){
q.push(trie[0][i]);
}
}
while(!q.empty()){
int u=q.front(); q.pop();
if(!fail[u]){
fail[u]=0;
}
for(int i=1; i<=26; i++){
if(trie[u][i]){
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
}else{
trie[u][i]=trie[fail[u]][i];
}
}
}
}
void query(string s0){
int u=0, res=0;
for(int i=0; i<s0.length(); i++){
u=trie[u][s0[i]-96];
for(int j=u; j&&num[j]; j=fail[j]){
if(num[u]){ans[num[u]]++;}
}
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while(cin>>N){
if(!N){break;}
AC h;
for(int i=1; i<=N; i++){
cin>>h.s[i];
}
h.build();
string ts; cin>>ts;
h.query(ts); int Ans=0;
for(int i=1; i<=N; i++){
Ans=max(h.ans[i], Ans);
}
cout<<Ans<<endl;
for(int i=1; i<=N; i++){
if(Ans==h.ans[i]){
cout<<h.s[i]<<endl;
}
}
}
return 0;
}