社区讨论
求助各位dalao们...我这个哪里写错了啊
P3796AC 自动机(简单版 II)参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6usx3w
- 此快照首次捕获于
- 2025/11/20 11:10 4 个月前
- 此快照最后确认于
- 2025/11/20 11:10 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
struct uio{
int son[27],end,fail;
}trie[1000001];
struct oiu{
int tot,pos;
}ans[151];
int n,cnt;
char c[151][1000001];
bool cmp(oiu x,oiu y)
{
return x.tot>y.tot;
}
void insert(char* a,int num)
{
int now=0,len=strlen(a);
for(int i=0;i<len;i++)
{
int c=int(a[i]-'a');
if(!trie[now].son[c])
trie[now].son[c]=++cnt;
now=trie[now].son[c];
}
trie[now].end=num;
}
void get_fail()
{
queue<int> que;
while(!que.empty()) que.pop();
for(int i=0;i<26;i++)
if(trie[0].son[i])
{
trie[trie[0].son[i]].fail=0;
que.push(trie[0].son[i]);
}
while(!que.empty())
{
int now=que.front();
que.pop();
for(int i=0;i<26;i++)
{
if(trie[now].son[i])
{
trie[trie[now].son[i]].fail=trie[trie[now].fail].son[i];
que.push(trie[now].son[i]);
}
else trie[now].son[i]=trie[trie[now].fail].son[i];
}
}
}
void query(char* a)
{
int now=0,len=strlen(a);
for(int i=0;i<len;i++)
{
now=trie[now].son[a[i]-'a'];
for(int j=now;j;j=trie[j].fail)
ans[trie[j].end].tot++;
}
}
int main()
{
scanf("%d",&n);
while(n)
{
memset(trie,0,sizeof(trie));
memset(ans,0,sizeof(ans));
cnt=0;
for(int i=1;i<=n;i++)
scanf("%s",c[i]),ans[i].pos=i,insert(c[i],i);
trie[0].fail=0;
get_fail();
scanf("%s",c[0]);
query(c[0]);
sort(ans+1,ans+1+n,cmp);
printf("%d\n",ans[1].tot);
for(int i=1;i<=n;i++)
if(ans[i].tot==ans[1].tot)
cout<<c[ans[i].pos]<<endl;
else break;
scanf("%d",&n);
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...