社区讨论
奇怪的问题
P3808AC 自动机(简单版)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lqgsc9vs
- 此快照首次捕获于
- 2023/12/22 23:27 2 年前
- 此快照最后确认于
- 2023/12/23 10:30 2 年前
rt
CPP#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
struct tree{
int fail;
int son[30];
int end;
}ac[1000100];
int cnt=1;//编号
void insert(string s){//正常tire建树
int len=s.length(),deep=0;
for(int i=0;i<len;i++){
int asc=s[i]-'a';
if(ac[deep].son[asc]==0){
ac[deep].son[asc]=cnt++;
}
deep=ac[deep].son[asc];
}
ac[deep].end+=1;
}
void fail(){//fail指针大放送
queue<int> q;//fail发放是基于bfs的
for(int i=0;i<26;i++){//第二层全部指向root
if(ac[0].son[i]!=0){//如果存在这个儿子
ac[ac[0].son[i]].fail=0;//压向root
q.push(ac[0].son[i]);//入队
}
}
while(!q.empty()){//不空
int u=q.front();q.pop();
for(int i=0;i<26;i++){//依旧遍历
if(ac[u].son[i]!=0){//如果存在这个儿子
ac[ac[u].son[i]].fail=ac[ac[u].fail].son[i];
//现在在遍历u.soni,所以u是他的爸爸
//所以a的fail为a的爸爸的fail的同名儿子
//如果没这个儿子,那正好为0,即指向root
q.push(ac[u].son[i]);
}else{//如果不存在
ac[u].son[i]=ac[ac[u].fail].son[i];
}
}
}
}//gg
int query(string s){//ac自动机的搜索主串
int len=s.length();//计算长度
int cnt=0;//当前的结点
int ans=0;
for(int i=0;i<len;i++){
int asc=s[i]-'a';
cnt=ac[cnt].son[s[i]-'a'];//儿子
for(int j=cnt;~j && ~ac[j].end;j=ac[j].fail){
ans+=ac[j].end;
ac[j].end=-1;//走过
}
}
return ans;//返回
}
int n;
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
while(n--){
cin>>s;
insert(s);
}
ac[0].fail=0;
fail();
cin>>s;
cout<<query(s)<<endl;
return 0;
}
以上100
CPP#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
struct tree{
int fail;
int son[30];
int end;
}ac[1000100];
int cnt=1;//编号
void insert(string s){//正常tire建树
int len=s.length(),deep=0;
for(int i=0;i<len;i++){
int asc=s[i]-'a';
if(ac[deep].son[asc]==0){
ac[deep].son[asc]=cnt++;
}
deep=ac[deep].son[asc];
}
ac[deep].end+=1;
}
void fail(){//fail指针大放送
queue<int> q;//fail发放是基于bfs的
for(int i=0;i<26;i++){//第二层全部指向root
if(ac[0].son[i]!=0){//如果存在这个儿子
ac[ac[0].son[i]].fail=0;//压向root
q.push(ac[0].son[i]);//入队
}
}
while(!q.empty()){//不空
int u=q.front();q.pop();
for(int i=0;i<26;i++){//依旧遍历
if(!ac[u].son[i]){//如果存在这个儿子
ac[ac[u].son[i]].fail=ac[ac[u].fail].son[i];
//现在在遍历u.soni,所以u是他的爸爸
//所以a的fail为a的爸爸的fail的同名儿子
//如果没这个儿子,那正好为0,即指向root
q.push(ac[u].son[i]);
}else{//如果不存在
ac[u].son[i]=ac[ac[u].fail].son[i];
}
}
}
}//gg
int query(string s){//ac自动机的搜索主串
int len=s.length();//计算长度
int cnt=0;//当前的结点
int ans=0;
for(int i=0;i<len;i++){
int asc=s[i]-'a';
cnt=ac[cnt].son[s[i]-'a'];//儿子
for(int j=cnt;~j && ~ac[j].end;j=ac[j].fail){
ans+=ac[j].end;
ac[j].end=-1;//走过
}
}
return ans;//返回
}
int n;
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
while(n--){
cin>>s;
insert(s);
}
ac[0].fail=0;
fail();
cin>>s;
cout<<query(s)<<endl;
return 0;
}
以上0
只是将33行的
CPP只是将33行的
if(ac[u].son[i]!=0){//如果存在这个儿子
改为
CPP if(!ac[u].son[i]){//如果存在这个儿子
就会这样,那下面的写法有问题吗
回复
共 1 条回复,欢迎继续交流。
正在加载回复...