AC自动机+路径压缩优化

acgoacgo

2025-12-05 19:35:35

发布于：广东

25阅读

0回复

0点赞

题目大意

给定 $n$ 个形如 $s\space t$ 的变换规则，再询问 $q$ 次，每次询问给出两个字符串 $s$ 和 $t$ ，计算有多少种单次替换能将 $s$ 变为 $t$ 。

题目分析

要从 $s$ 中找替换规则中的子串，显然是一个多模式匹配问题，可以使用AC自动机解决。
接下来就该思考如何将两个字符串转换为一个字符串，因为AC自动机适用于单个串匹配，如果不进行转换，每次都要以 $O(|t|)$ 的时间复杂度比较。以下思路参考了洛谷用户@Register_int：
把变换 $s\rightarrow t$ 记为 $A?CD?B$ ，其中 $A,B,C,D$ 都为字符串， $A$ 和 $B$ 分别表示 $s$ 和 $t$ 的最长公共前缀和后缀， $C$ 和 $D$ 分别表示 $s$ 和 $t$ 其它的部分，对询问也进行同样的变换。
正确性说明：若变换 $s\rightarrow t$ 是一个合法的变换，设它表示为 $E?GH?F$ ， $E$ 实际上不会影响开头和结尾未触及的部分，即未被修改的部分必然完全相同，且这部分就位于字符串的两端。而中间需要进行变换的部分， $G$ 一定对应 $C$ ， $H$ 一定对应 $D$ ，即改变了需要改变的位置。这样不需要改变的部分没有改变，需要改变的部分改变了，即这个变换可行。
变换中的 $?$ 可以变为'{'，因为它位于 $'z'$ 之后。

变换代码如下：

inline string sub(string s,int l,int r) {return s.substr(l,r-l+1);} //求子串
inline string f(string s,string t)
{
	int i=0,j=0,len=min(s.size(),t.size());
	while (i<len && s[i]==t[i]) i++; //找最长公共前缀
	while (j<len && s[s.size()-j-1]==t[t.size()-j-1]) j++; //找最长公共后缀
	return sub(s,0,i-1)+"{"+sub(s,i,s.size()-j-1)+sub(t,i,t.size()-j-1)+"{"+sub(s,s.size()-j,s.size()-1);
}

求 $fail$ 指针和AC自动机操作代码如下：

inline void getfail()
{
	queue<int> q;
	for (int i=0;i<27;i++) //注意是27，辅助字符占用一个
	{
		if (t[0].son[i])
			q.push(t[0].son[i]);
	}
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<27;i++)
		{
			if (t[now].son[i])
			{
				t[t[now].son[i]].fail=t[t[now].fail].son[i]; //子节点的fail指针=父节点的fail指针的对应子节点
			}
			else
				t[now].son[i]=t[t[now].fail].son[i]; //若不存在，不能不管，否则会忽略特殊情况
		}
	}
}
inline int query(string s)
{
	int now=0,ans=0;
	for (auto c:s)
	{
		c-='a';
		now=t[now].son[c];
		int i=now;
        //last是上一次操作的编号，tot是当前操作编号
        //若last=tot，说明当前操作已经进行，不用再进行
        //这样的好处是不用每次都重置标记，如果只使用bool vis，每次询问后都要清空vis
		while (i && t[i].last!=tot)
			ans+=t[i].end,t[i].last=tot,i=t[i].fail; //不清楚是否有重复变换，因此是+=end，记得更新last
	}
	return ans;
}

这样做时间复杂度最坏情况下能达到 $O((\sum_{i=1}^{n} s_{i,1}+s_{i,2})^2)$ 量级，能得到 $90$ 分。

优化

接下来考虑优化。

AC自动机常用的优化方法是拓扑排序优化，但拓扑排序优化需要遍历整个字典树，甚至可能提高时间复杂度，因此拓扑排序优化不可行。

我们注意到，在查询过程中，实际上访问了大量重复字符，一些 $end$ 标记为 $0$ 的节点也被访问了。为了避免这种情况，可以使用后缀链跳跃的方法，为每个节点定义 $next$ 为当前后缀链上下一个有 $end$ 标记的节点，这样操作时每个模式串只访问一次，与 $t$ 的长度无关。

如何求得 $next$ ？分两种情况，若 $fail$ 指针指向的节点带有 $end$ 标记，直接指向它，否则继承它的 $next$ ，代码如下：

if (t[t[t[now].fail].son[i]].end)
    t[t[now].son[i]].nxt=t[t[now].fail].son[i];
else
    t[t[now].son[i]].nxt=t[t[t[now].fail].son[i]].nxt;

这时候 $query$ 函数的 $i=t[i].fail$ 就可以改为 $i=t[i].nxt$

完整代码

#include<bits/stdc++.h>
using namespace std;

int n,cnt=0,tot;
//cnt：字典树大小，tot：当前测试编号
struct node
{
	int son[27],fail,end,last,nxt;
    //end：以当前节点为结尾的字符串数，last：上一次操作时的测试编号，nxt：后缀链上下一个带有标记的节点
} t[5000005];
inline void build(string s) //构建节点
{
	int now=0;
	for (auto c:s)
	{
		c-='a';
		if (!t[now].son[c]) t[now].son[c]=++cnt;
		now=t[now].son[c];
	}
	t[now].end++; //不清楚是否有重复节点，++
}
inline void getfail() //求fail指针
{
	queue<int> q;
	for (int i=0;i<27;i++)
	{
		if (t[0].son[i])
			q.push(t[0].son[i]);
	}
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<27;i++)
		{
			if (t[now].son[i])
			{
				t[t[now].son[i]].fail=t[t[now].fail].son[i]; //求fail指针
				if (t[t[t[now].fail].son[i]].end) t[t[now].son[i]].nxt=t[t[now].fail].son[i];  //求nxt指针
				else t[t[now].son[i]].nxt=t[t[t[now].fail].son[i]].nxt;
				q.push(t[now].son[i]);
			}
			else
				t[now].son[i]=t[t[now].fail].son[i];
		}
	}
}
inline int query(string s) //查询
{
	int now=0,ans=0;
	for (auto c:s)
	{
		c-='a';
		now=t[now].son[c];
		int i=now;
		while (i && t[i].last!=tot)
			ans+=t[i].end,t[i].last=tot,i=t[i].nxt; //i=t[i].fail升级版
	}
	return ans;
}
inline string sub(string s,int l,int r) {return s.substr(l,r-l+1);} //子串函数，获取[l,r]的子串
inline string f(string s,string t) //变换
{
	int i=0,j=0,len=min(s.size(),t.size());
	while (i<len && s[i]==t[i]) i++;
	while (j<len && s[s.size()-j-1]==t[t.size()-j-1]) j++;
	return sub(s,0,i-1)+"{"+sub(s,i,s.size()-j-1)+sub(t,i,t.size()-j-1)+"{"+sub(s,s.size()-j,s.size()-1);
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	string s,t;
	int q;
	cin >> n >> q;
	for (int i=1;i<=n;i++)
	{
		cin >> s >> t;
		build(f(s,t));
	}
	getfail();
	for (int i=1;i<=q;i++)
	{
		tot=i;
		cin >> s >> t;
		cout << query(f(s,t)) << '\n';
	}
	return 0;
}