社区讨论

奇怪的问题

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
			if(ac[u].son[i]!=0){//如果存在这个儿子
改为
CPP
			if(!ac[u].son[i]){//如果存在这个儿子
就会这样,那下面的写法有问题吗

回复

1 条回复,欢迎继续交流。

正在加载回复...