失配树学习笔记

pengchujie / 2023-08-26 / 原文

传送门

考虑把原字符串先\(kmp\)一遍，求出以\(i\)结尾的前缀的最长\(border\)，根据\(border\)的\(border\)还是\(border\)这个定理，我们在寻找前缀\(p\)和前缀\(q\)的最长公共\(border\)时，我们可以考虑运用这个定理，一直往前跳，找到最先一样的\(border\)，这就是最长公共\(bordedr\)，至于优化，我们可以使用倍增

细节，\(border\)不能是自身，所以在\(p\)跳完\(border\)后即使是为\(q\)，也不能直接输出\(q\)。

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+50;
char s[N];
ll n,m,fa[N][22],dep[N],p,q;
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	fa[0][0]=fa[1][0]=0,dep[0]=0,dep[1]=1;
	for(ll i=2,j=0;i<=n;i++)
	{
		while(j!=0&&s[j+1]!=s[i]) j=fa[j][0];
		if(s[j+1]==s[i]) j++;
		fa[i][0]=j,dep[i]=dep[j]+1;
	}
	for(ll i=1;i<=21;i++)
	for(ll j=1;j<=n;j++)
	fa[j][i]=fa[fa[j][i-1]][i-1];
	scanf("%lld",&m);
	while(m--)
	{
		scanf("%lld %lld",&p,&q);
		if(dep[p]<dep[q]) swap(p,q);
		for(ll i=21;i>=0;i--) if(dep[fa[p][i]]>=dep[q]) p=fa[p][i];
		for(ll i=21;i>=0;i--) if(fa[p][i]!=fa[q][i]) p=fa[p][i],q=fa[q][i];
		printf("%lld\n",fa[p][0]);
	}
	return 0;
}