P5829 【模板】失配树

题目：

在这里插入图片描述

题解：

参考题解
我们先想一个问题：如何求出一个字符串的所有border？
如果一个字符串既是 S的前缀又是 S 的后缀，那么我们把 SS 自己平移一下就可以前后重合，然后我们就可以继续匹。。。。。这不就是KMP吗
在这里插入图片描述
求两个前缀的最长公共border，
先对原串进行KMP，通过跳两个前缀的next求到两个前缀的所有border
我们通过next数组构建一棵树（发现这就是只有一个字符串的AC自动机的fail树，所有我们也叫它fail树），容易发现两个前缀的最长公共border就是他们在fail树上的LCA

综上所述：

  1. 对原串KMP一遍，求的next数组
  2. 构建fail树
  3. 在fail数上跑LCA

    代码：

#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;
}