好像求不出后缀模式串,是循环求解有问题吗? (还是指针出问题?)
#include<bits/stdc++.h>
using namespace std;
int n,q,ton[151],tn,ans;
string str[152];
queue<string> anss;
struct node {
int cnt;
node *fail,*nxt[26];
};
node *trie;
inline int tra(char a){
return a-'a';
}
inline void insert(string s){
int l=s.size();
node *p=trie;
for(int i=0;i<l;i++){
int num=tra(s[i]);
if(p->nxt[num]==NULL){
p->nxt[num]=new (node) {0,NULL};
}
p=p->nxt[num];
}
(p->cnt)=tn;
return;
}
void Fail(void){
node *p=trie;
queue<node*> q;
for(int i=0;i<26;i++){
if(p->nxt[i]!=NULL){
p->nxt[i]->fail=trie;
q.push(p->nxt[i]);
}else p->nxt[i]=trie;
}
while(!q.empty()){
p=q.front();
q.pop();
for(int i=0;i<26;i++){
if(p->nxt[i]!=NULL){
p->nxt[i]->fail=p->fail->nxt[i];
q.push(p->nxt[i]);
}else p->nxt[i]=p->fail->nxt[i];
}
}
}
void sch(string s){
int l=s.size();
node *p=trie;
for(int i=0;i<l;i++){
int num=tra(s[i]);
p=p->nxt[num];
for(node *j=p->fail;j;j=j->fail){
ton[p->cnt]++;
//cout<<i+1<<' '<<p->cnt<<' '<< ton[p->cnt]<<"(find)"<<endl;//Debug
}
}
return;
}
int main(){
while(cin>>n){
if(n==0) break;
for(int i=1;i<=n;i++) ton[i]=0;
tn=1;
trie=new (node) {0,NULL};
for(int i=1;i<=n;i++,tn++)
{
cin>>str[i];
insert(str[i]);
}
Fail();
cin>>str[n+1];
sch(str[n+1]);
ans=0;
for(int i=1;i<=n;i++){
if(ton[i]>ans){
ans=ton[i];
while(!anss.empty()) anss.pop();
}
if(ton[i]>=ans) anss.push(str[i]);
}
printf("%d\n",ans);
for(;!anss.empty();anss.pop()){
cout<<anss.front()<<endl;
}
}
return 0;
}