AC自动机【萌新文章】

我这个蒟蒻第一次写博客，有点小激动呢。

主要是最近刚学了AC自动机，学得糟糟糕糕，记录一下，看到dalao们都在写博客，决定自己也写一波【我好水的啦，写的也不好】

AC自动机大概就是 Trie+KMP=AC自动机

嗯，在KMP中，引入了字符串失配最优转移方案：失配函数f[i]，在j位匹配失败后，便转到f[j]位匹配

同样的道理，AC自动机就是升维的KMP，在匹配时不仅要考虑当前模板串，还要顾及其它模板串，所以失配函数还要顾及其它模板串，匹配成功也要考虑其它模板串

所以，AC自动机采用了bfs构造f[]，还引入了last[]后缀链接，用以指向当前串匹配成功时同时可以匹配成功的串

具体来讲AC自动机有三个操作

插入：

与trie树的插入方式相同

void insert(int id)

{

	int u=0;

	for(int i=0;i<len[id];i++)

	{

		int v=P[i]-'a';

		if(!ch[u][v])

		{

			ch[u][v]=++siz;

			fill(ch[siz],ch[siz]+26,0);

		}

		u=ch[u][v];

	}

	val[u]=id;

}

构造失配函数：

这里采用了优化方法，将子节点不存在的子节点指针直接指向f[]函数指向节点的子节点，然后在匹配时甚至可以不用f[]函数，因为在构造时已经提前把匹配不成功时的指向指向了f[]指针，这能节省不少时间。

总的过程采用bfs构造f[],同时构造last,通过f[]检查是否可以转移

具体思想与KMP相同

void getfail()

{

	queue<int> q;

	for(int i=0;i<26;i++) if(ch[0][i]) q.push(ch[0][i]);

	int u,v;

	while(!q.empty())

	{

		u=q.front();

		q.pop();

		for(int i=0;i<26;i++)

		{

			v=ch[u][i];

			if(!ch[u][i])

			{

				ch[u][i]=ch[f[u]][i];

				continue;

			}

			q.push(v);

			f[v]=ch[f[u]][i];

			last[v]=val[f[v]] ? f[v]:last[f[v]];

		}

	}

}

匹配：

void AC()

{

	vis[0]=true;

	ans=0;

	char c=getchar();

	int id,u=0;

	while(!isalpha(c)) c=getchar();

	for(int i=1;isalpha(c);i++)

	{

		vis[i]=false;

		id=c-'a';

		u=ch[u][id];

		if(val[u]) print(u);

		else if(last[u]) print(last[u]);

		c=getchar();

	}

}

print为沿着last的打印函数

嗯就这样

巴特西

AC自动机【萌新文章】

最新文章

热门文章