社区讨论
求助tle
P3808AC 自动机(简单版)参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lobx4bx5
- 此快照首次捕获于
- 2023/10/30 04:22 2 年前
- 此快照最后确认于
- 2023/11/04 09:28 2 年前
CPP
#include<iostream>
#include<cstdio>
using namespace std;
int n,t=1;
int bo[10000000];
int ch[26][1000000];
int que[10000000];
int nxt[10000000];
int ans;
void insert(string a)
{
int u=1;
for(int i=0;i<a.length();i++)
{
int c=a[i]-'a';
if(ch[c][u]==0)
{
t++;
ch[c][u]=t;
}
u=ch[c][u];
}
bo[u]++;
}
void bfs()
{
for(int i=0;i<=25;i++)
ch[i][0]=1;
que[1]=1;
nxt[1]=0;
for(int q1=1,q2=1;q1<=q2;q1++)
{
int u=que[q1];
for(int i=0;i<=25;i++)
{
if(!ch[i][u])ch[i][u]=ch[i][nxt[u]];
else
{
que[++q2]=ch[i][u];
int v=nxt[u];
while(v>0&&!ch[i][v])v=nxt[v];
nxt[ch[i][u]]=ch[i][v];
}
}
}
}
void find(string s)
{
int u=1;
for(int i=0;i<s.length();i++)
{
int c=s[i]-'a';
int k=ch[c][u];
while(k>1)
{
ans+=bo[k];
bo[k]=0;
k=nxt[k];
}
u=ch[c][u];
}
return;
}
int main()
{
scanf("%d",&n);
string a;
for(int i=1;i<=n;i++)
{
cin>>a;
insert(a);
}
bfs();
string s;
cin>>s;
find(s);
cout<<ans;
}
为什么书上nxt数组构建中,else内有while语句
回复
共 0 条回复,欢迎继续交流。
正在加载回复...