题解 P5829 【【模板】失配树】
WYXkk
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}$ 都可以）。
代码如下：
```cpp
#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}$ 的
```cpp
#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;
}
```