社区讨论

这个数据?

P3808AC 自动机(简单版)参与者 5已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mikdevng
此快照首次捕获于
2025/11/29 22:12
3 个月前
此快照最后确认于
2025/12/01 19:25
3 个月前
查看原帖
警示后人:记得在 mainmain 中调用处理 failfail 指针的函数。
CPP
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e6+5;
int n;
string s[N],t;
struct ACt{
	struct Node{
		int ch[27];
		int fail;
		int flag;
		Node(){
			memset(ch,0,sizeof ch);
			fail=flag=0;
		}
	}tr[N];
	int tot=0;
	void insert(string s){
		int p=0;
		for(char c:s){
			int to=c&31;
			if(!tr[p].ch[to]) tr[p].ch[to]=++tot;
			p=tr[p].ch[to];
		}
		tr[p].flag++;
	}
	void prepare(){
		queue<int> q;
		int p=0;
		q.push(p);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			if(u==0){
				for(int i=1;i<=26;i++)
				if(tr[u].ch[i]) q.push(tr[u].ch[i]);
				continue;
			}
			for(int i=1;i<=26;i++)
			if(tr[u].ch[i]){
				int v=tr[u].ch[i];
				q.push(v);
				p=tr[u].fail;
				while(p&&!tr[p].ch[i]) p=tr[p].fail;
				if(tr[p].ch[i]) tr[v].fail=tr[p].ch[i];
				else tr[v].fail=0;
			}
		}
	}
	int run(string s){
		int cnt=0,p=0;
		for(char c:s){
			int to=c&31;
			cnt+=tr[p].flag;
			tr[p].flag=0;
			while(p&&!tr[p].ch[to]){
				p=tr[p].fail;
				cnt+=tr[p].flag;
				tr[p].flag=0;
			}
			if(tr[p].ch[to]) p=tr[p].ch[to];
			cnt+=tr[p].flag;
			tr[p].flag=0;
		}
		return cnt;
	}
}act;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		act.insert(s[i]);
	}
	cin>>t;
	cout<<act.run(t);
	return 0;
}
打完后忘了在 mainmain 中加 prepareprepare,结果还过了 50pts50pts,害得我找了半天 failfail 指针的问题才发现没把 prepareprepare 打进去。。。

回复

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

正在加载回复...