社区讨论
舅舅孩子吧,一晚上了。
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 条回复,欢迎继续交流。
正在加载回复...