自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:14:44，当前版本为作者最后更新于2019-12-19 09:35:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5829 【模板】失配树 题解

题意简述

给你一个串 $S$，定义一个字符串的 $\text{border}$ 为它的非本身的既是它的前缀又是它的后缀的字符串，$m$ 次询问，每次询问给定两个数 $i,j$，询问 $S_{1...i}$ 和 $S_{1...j}$ 的最长公共 $\text{border}$。

$1\le|S|\le10^6,1\le i,j\le|S|,1\le m\le10^5$，字符集为 $26$ 个小写字母。

解法

首先我们来看另外一个与它相关的问题：如何求出一个字符串的所有 $\text{border}$？

如果一个字符串既是 $S$ 的前缀又是 $S$ 的后缀，那么我们把 $S$ 自己平移一下就可以前后重合，然后我们就可以继续匹。。。。。诶？这不是 $\text{KMP}$ 么？

所以我们对原串 $\text{KMP}$ 一遍，然后就可以发现，$S_{1\cdots next(|S|)}$ 和 $S_{|S|-next(|S|)+1\cdots |S|}$ 是完全一样的！于是 $S^\prime=S_{1\cdots next(|S|)}$ 就是 $S$ 的一个 $\text{border}$。

那么 $S$ 是否还有其他 $\text{border}$ 呢？有。根据上文，$S^{\prime\prime}= S_{1\cdots next(next(|S|))}$ 是 $S^\prime=S_{1\cdots next(|S|)}$ 的一个 $\text{border}$，于是 $S^{\prime\prime}$ 既是 $S^\prime$ 的前缀又是 $S^\prime$ 的后缀。由于 $S^\prime$ 既是 $S$ 的后缀又是 $S$ 的前缀，所以 $S^{\prime\prime}$ 既是 $S$ 的前缀的前缀又是 $S$ 的后缀的后缀，所以 $S^{\prime\prime}$ 既是 $S$ 的前缀又是 $S$ 的后缀，也是 $S$ 的 $\text{border}$。

以此类推，我们可以得到，$S$ 的所有 $\text{border}$ 为：$S_{1\cdots next(|S|)},S_{1\cdots next(next(|S|))},S_{1\cdots next(next(next(|S|)))},\cdots$。

我们再来看看原题：求两个前缀的最长公共 $\text{border}$。

老套路，先对原串 $\text{KMP}$ 一遍，于是我们可以通过跳两个前缀的 $next$ 求到两个前缀的所有 $\text{border}$。

等等，这不是暴力求 $\text{LCA}$ 的思路吗？先暴力找到所有祖先，再判断相交。

所以我们可以通过 $next$ 数组建一棵树出来（可以发现这就是只有一个字符串的 $\text{AC}$ 自动机的 $fail$ 树，所以我们也叫它 $fail$ 树），容易发现两个前缀的最长公共 $\text{border}$ 就是它们在 $fail$ 树上的 $\text{LCA}$（当它们是祖先—后代关系时除外，此时结果是祖先的父亲）。

综上所述，本题的做法如下：

• 对原串 $\text{KMP}$ 一遍，求出 $next$ 数组；
• 构建 $fail$ 树；
• 在 $fail$ 树上跑 $\text{LCA}$（倍增和 $\text{tarjan}$ 都可以）。

代码如下：

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

const int N=1000005;
int fa[N][22],n,m,dep[N];char s[N];
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	fa[0][0]=fa[1][0]=0,dep[0]=0,dep[1]=1;
	for(ri 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;
	}
	//以上为kmp
	//以下为倍增lca
	F(i,1,21) F(j,1,n) fa[j][i]=fa[fa[j][i-1]][i-1];
	rd(m);
	while(m--)
	{
		int x,y;rd(x);rd(y);if(dep[x]<dep[y]) swap(x,y);
		UF(i,21,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		UF(i,21,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
		printf("%d\n",fa[x][0]);
	}
	return 0;
}

突然感觉这题有种强行二合一的感觉（

倍增不开 $-\text O2$ 太慢了，有几个点会 $900ms$。。。这里再贴个 $\text{tarjan}$ 的

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

const int N=1000005;
int next[N],n,m;char s[N];
int fa[N];int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}void merge(int x,int y){if((x=get(x))!=(y=get(y)))fa[x]=y;}
bool vis[N];
int head[N],to[2*N],nxt[2*N],tot;void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}//graph
int head2[N],to2[2*N],nxt2[2*N],num[2*N],tot2;void add2(int u,int v,int w){to2[++tot2]=v;num[tot2]=w;nxt2[tot2]=head2[u];head2[u]=tot2;}//query
int ans[N],x[N],y[N];
void tarjan(int x)
{
	vis[x]=true;
	for(ri i=head[x];i;i=nxt[i]) if(!vis[to[i]]) {tarjan(to[i]);merge(to[i],x);}
	for(ri i=head2[x];i;i=nxt2[i]) if(vis[to2[i]]) ans[num[i]]=get(to2[i]);
}
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	next[0]=next[1]=0;F(i,1,n) fa[i]=i;
	for(ri i=2,j=0;i<=n;++i)
	{
		while(j!=0&&s[j+1]!=s[i]) j=next[j];
		if(s[j+1]==s[i]) ++j;
		next[i]=j;
	}
	F(i,1,n) add(next[i],i);
	rd(m);
	F(i,1,m){rd(x[i]);rd(y[i]);add2(x[i],y[i],i);add2(y[i],x[i],i);}
	tarjan(0);
	F(i,1,m) printf("%d\n",(ans[i]==x[i]||ans[i]==y[i])?next[ans[i]]:ans[i]);
	return 0;
}