AC自动机 WA #2
查看原帖
AC自动机 WA #2
567522
Yuzilihhh楼主2024/7/2 21:36
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define lf long double
#define INF 0x7fffffff
#define debug(alpha) cout<<alpha<<endl
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define Max3(a,b,c) (max(max((a),(b)),(c)))
#define Min3(a,b,c) (min(min((a),(b)),(c)))
using namespace std;
namespace io
{
	template<typename T> inline void iread(T &x114){
		char c=' ';int wx114=1;x114=0;
		while(!isdigit(c)){c=getchar();if(c=='-')wx114=-1;}
		while(isdigit(c)){x114=x114*10+c-'0';c=getchar();}
		x114*=wx114;
	}
	template<typename T> inline void write(T x114){
		if(x114==0){putchar('0');return;}
		if(x114<0){putchar('-');x114=-x114;}
		int stk[50],top=0;
		while(x114){stk[++top]=x114%10;x114/=10;}
		while(top) putchar(stk[top--]+'0');
	}
}
/**
 * AC自动机是一个很好用的东西
 * 完美融合了KMP和Trie
 * 多模式串匹配非常有效率
 * 大体思路就是把模式串建成一棵Trie
 * 然后拉出各种失配指针,失配就去到另一个节点
 * 最后统计出来结果
 * 总之对初学者来讲,难度较高
 */
const int N=1e6+100;
int n;// 模式串个数
struct node
{
	int son[26];// 每个Trie节点都有a~z儿子(有些为空)
	// 以及转移边
	/*
	 转移边就是在我失配的情况下,我转移到另一个模式串去
	 一个节点可以有多条转移边,但只有一条回跳边
	 */
}trie[N];
int idx;// 最新节点编号
// 根节点是0
int cnt[N];// 以该节点为结尾的单词数
void insert(string s)// 插入一个模式串,不会复习Trie
{
	int l=s.length(),p=0;
	for(int i=0;i<l;++i)
	{
		char c=s[i];
		if(!trie[p].son[c-'a'])
			trie[p].son[c-'a']=++idx;
		p=trie[p].son[c-'a'];
	}
	++cnt[p];
}
int fail[N];// 回跳边存储,指向回跳的位置
void build()// 建立转移边和回跳边
{
	queue<int> q;
	for(int i=0;i<26;++i)
		if(trie[0].son[i])// 只要我这个位置有数据
			q.push(trie[0].son[i]);// 作为起点
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;++i)
		{
			if(trie[u].son[i])// 我有对应的儿子,建立回跳边
			{
				fail[trie[u].son[i]]=trie[fail[u]].son[i];
				// 我儿子的回跳边是 我回跳边所指的节点的 对应的儿子
				q.push(trie[u].son[i]);
			}
			else// 我没有对应的儿子,建立转移边
				trie[u].son[i]=trie[fail[u]].son[i];
				// 直接指向我回跳边所指节点的 对应的儿子
			// 总之我有儿子就让儿子指,没儿子我自己指
		}
	}
}
int query(string s)// 查找模式串
{
	int l=s.length();
	int ans=0;// 记录答案数
	for(int k=0,i=0;k<l;++k)
	{
		// 这里i是一个指针,指向现在所遍历的位置
		i=trie[i].son[s[k]-'a'];
		for(int j=i;j&&(~cnt[j]);j=fail[j])
		{
			// 如果~cnt[i]==false,说明之前走过了,撤退
			// 不然还可以接着回跳边跳
			ans+=cnt[j];
			cnt[j]=-1;
		}
	}
	return ans;
}
string sss;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>sss;
		insert(sss);
	}
	cin>>sss;
	cout<<query(sss);
	return 0;
}

多行注释之前的不用管,下面的代码第二个点WA了

2024/7/2 21:36
加载中...