社区讨论

舅舅孩子吧,一晚上了。

P3796AC 自动机(简单版 II)参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lobq5eeo
此快照首次捕获于
2023/10/30 01:07
2 年前
此快照最后确认于
2023/11/04 05:45
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int LEN=300010,N=10010;
int n;
int trie[LEN][26],ed[LEN],fail[LEN];
char t[LEN][200],s[LEN];
int ans[LEN];
int cnt;
void insert(char t[LEN],int v){
	int p=0;
	int len=strlen(t);
	for(int i=0;i<len;++i){
		int ch=t[i]-'a';
		if(!trie[p][ch]) trie[p][ch]=++cnt;
		p=trie[p][ch];
	}
	ed[p]=v;
}
void bfs(){
	queue<int> q;
	for(int i=0;i<26;++i){
		if(trie[0][i]){
			fail[trie[0][i]]=0;
			q.push(trie[0][i]);
		}
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<26;++i){
			if(trie[now][i]){
				fail[trie[now][i]]=trie[fail[now]][i];
				q.push(trie[now][i]);
			}
			else trie[now][i]=trie[fail[now]][i];
		}
	}
}
void check(){ 	
	int now=0;
	int len=strlen(s);
	for(int i=0;i<len;++i){
		now=trie[now][s[i]-'a'];
		for(int j=now;j;j=fail[j]){
			ans[ed[j]]++;
		}
	}
}
int main(){
	while(scanf("%d",&n)&&n!=0){
		memset(trie,0,sizeof trie);
		memset(ed,0,sizeof ed);
		memset(fail,0,sizeof fail);
		memset(ans,0,sizeof ans);
		cnt=0;
		for(int i=1;i<=n;++i){
			scanf("%s",t[i]);
			insert(t[i],i);
		}
		bfs();
		scanf("%s",s);
		check();
		int tmp=0;
		for(int i=1;i<=n;++i) if(ans[i]>tmp) tmp=ans[i];
		printf("%d\n",tmp);
		for(int i=1;i<=n;++i) if(ans[i]==tmp) printf("%s\n",t[i]);
	}
	return 0;
}
就是91分,一个点过不去,想下载数据却下不了

回复

2 条回复,欢迎继续交流。

正在加载回复...