求助AC自动机
查看原帖
求助AC自动机
531477
chenrui_楼主2023/9/4 17:11

好像求不出后缀模式串,是循环求解有问题吗? (还是指针出问题?)

#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;
}
2023/9/4 17:11
加载中...