标准的ac自动机写法,但是结果总是差一个字母没输出
查看原帖
标准的ac自动机写法,但是结果总是差一个字母没输出
298573
wohen233cai楼主2020/8/1 18:29

运行结果总是差一个字母或不差,但是次数统计是正确的,求大佬帮助:<)

//#pragma GCC optimize(2) 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cctype>
#include<cstring>
#include<string>
#define mkp(a,b) make_pair(a,b)
#define ipar pair<int,int>
#define gc getchar
#define ll long long
#define endl '\n'
#define rep(i,a,b) for(int i = a;i <= b;++i)
#define drp(i,a,b) for(int i = a;i >= b;--i)
#define FOR(i,a,b) for(int i = a;i < b;++i)
using namespace std;

const int N = 4e3+5,inf = 0x3f3f3f3f,md = 1000000007;

int trie[N][26]; //字典树
int wds[N];	//记录了第i个模式串的输入次数 
int fail[N];	//记录第i个节点的fail值
int record[N]; //记录第i个模式串的出现次数 
char wd[N][72]; //记录第i个串的内容
int cnt;

void build_trie(char* ch){
	int rt = 0,len = strlen(ch);
	FOR(i,0,len){
		int id = ch[i]-'a';
		if(!trie[rt][id])trie[rt][id]=++cnt;
		rt=trie[rt][id];
	}
	wds[rt]=1;
	memcpy(wd[rt],ch,sizeof ch);
}

void build_fail(){
	queue<int>q;
	int rt = 0;
	FOR(i,0,26){
		if(trie[0][i]){
			q.push(trie[0][i]);
			fail[trie[0][i]]=0;
		}
	}
	while(!q.empty()){
		rt = q.front();q.pop();
		FOR(i,0,26){
			if(trie[rt][i]){
				q.push(trie[rt][i]);
				fail[trie[rt][i]] = trie[fail[rt]][i];
			}else{
				trie[rt][i]=trie[fail[rt]][i];
			}
		}
	}
}

void query(char* ch){
	int rt = 0,len = strlen(ch);
	FOR(i,0,len){
		rt = trie[rt][ch[i]-'a'];
		for(int j = rt;j;j=fail[j]){
			record[j]+=wds[j];
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	int n;
	char ch[1000005];
	while(cin>>n && n){
		memset(record,0,sizeof(record));
		memset(fail,0,sizeof fail);
		memset(trie,0,sizeof trie);
		memset(wds,0,sizeof wds);
		memset(wd,0,sizeof wd);
		cnt = 0;
		FOR(i,0,n){
			cin >> ch;
			build_trie(ch);
		}	
		cin >> ch;
		build_fail();
		query(ch);
		vector<int> res;
		int t = 0;
		rep(i,1,cnt){
			if(t < record[i]){
				t = record[i];
				res.clear();
				res.push_back(i);
			}else if(t==record[i]&&t)
				res.push_back(i);
		}
		cout << t << endl;
		FOR(i,0,res.size()){
			cout << wd[res[i]] << endl; 
		}
	}
	return 0;
}	
2020/8/1 18:29
加载中...