社区讨论
求助,是不是数组大小有问题
P3796AC 自动机(简单版 II)参与者 4已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @mi6x9bbr
- 此快照首次捕获于
- 2025/11/20 12:19 4 个月前
- 此快照最后确认于
- 2025/11/20 12:19 4 个月前
RE了大部分点,开大了却又WA了
CPP#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 155;
int n;
char str[maxn][maxn];
struct AC_automation{
int ch[maxn][26],val[maxn],fail[maxn],trank[maxn],cnt;
queue<int>q;
//s从1开始
void clear (){
cnt=0;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
memset(fail,0,sizeof(fail));
memset(trank,0,sizeof(trank));
}
void insert (char *s,int id){
int now=0,v;
while (*(++s)){
v=(*s)-'a';
if (!ch[now][v]) ch[now][v]=++cnt;
now=ch[now][v];
}
val[now]++,trank[now]=id;
}
void build (){
for (int i=0;i<=25;i++)
if (ch[0][i])
fail[ch[0][i]]=0,q.push(ch[0][i]);
while (!q.empty()){
int u=q.front();
q.pop();
for (int i=0;i<=25;i++){
if (ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
else ch[u][i]=ch[fail[u]][i];
}
}
}
//s从1开始
void query (char *s){
int ans[maxn],last[maxn][151],now=0,v,mx=-1;
for (int i=0;i<26;i++)ans[i]=0;
for (int i=0;i<maxn;i++)last[i][0]=0;
while (*(++s)){
v=(*s)-'a';
now=ch[now][v];
int temp=now;
while (temp){
if (val[temp]){
ans[trank[temp]]+=val[temp];
mx=max(mx,ans[trank[temp]]);
last[ans[trank[temp]]][++last[ans[trank[temp]]][0]]=trank[temp];
}
temp=fail[temp];
}
}
printf("%d\n",mx);
sort(last[mx]+1,last[mx]+last[mx][0]+1);
for (int i=1;i<=last[mx][0];i++)
printf("%s\n",str[last[mx][i]]+1);
}
}AC;
int main ()
{
scanf("%d",&n);
while(n){
AC.clear();
for (int i=1;i<=n;i++) scanf("%s",str[i]+1),AC.insert(str[i],i);
AC.build();
scanf("%s",str[0]+1);
AC.query(str[0]);
scanf("%d",&n);
}
return 0;
}
回复
共 10 条回复,欢迎继续交流。
正在加载回复...