洛谷P5829 【模板】失配树 题解

题目链接：P5829 【模板】失配树

题意：

给定一个字符串 $s$，定义它的 $k$ 前缀 $\mathsf{pre}_k$ 为字符串 $s_{1\dots k}$，$k$ 后缀 $\mathsf{suf}_k$ 为字符串 $s_{|s|-k+1\dots |s|}$，其中 $1 \le k \le |s|$。

定义 $\mathrm{Border}(s)$ 为对于 $i \in [1, |s|)$，满足 $\mathsf{pre}_i = \mathsf{suf}_i$ 的字符串 $\mathsf{pre}_i$ 的集合。$\mathrm{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。

有 $m$ 组询问，每组询问给定 $p,q$，求 $s$ 的 $\boldsymbol{p}$ 前缀 和 $\boldsymbol{q}$ 前缀 的 最长公共 $\operatorname{border}$ 的长度。

输入格式：

第一行一个字符串 $s$。

第二行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $p,q$。

输出格式：

对于每组询问，一行一个整数，表示答案。若不存在公共 $\operatorname{border}$，请输出 $0$。

数据范围：

$1\leq p,q \le |s|\leq 10^6$，$1 \leq m \leq 10^5$，$s_i \in [\texttt{a}, \texttt{z}]$。

就硬搞个模板题呗，不如直接去做 AC 自动机板子

显然就是跑一遍 kmp ，然后在 fail 树上面搞。

注意到前缀 $p,q$ 的最长公共 border其实就是 $p$ 和 $q$ 在树上的 LCA

不过有个特例， $p,q$ 中有一个为 LCA 时，答案就是 LCA 的父亲，因为 border 不能和原长相等。

其实实现的时候只需要查一下 $\,\mathsf{fa}(p),\mathsf{fa}(q)$ 的 LCA 就好了

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define fail(x) (fa[x][0])
#define N ((int)(1e6 + 15))

char s[N];
int n,dep[N],lg[N],fa[N][22];
int lca(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if(x == y) return x;
    for(int i=lg[dep[x]]; ~i; i--)
        if(fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; }
    return fa[x][0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    cin >> (s + 1); n = strlen(s + 1);
    lg[1] = 0 + 1; fa[1][0] = 0; dep[0] = 1; dep[1] = 2;
    for(int i=2; i<=n; i++) lg[i] = lg[i >> 1] + 1;
    for(int i=2, j=0; i<=n; i++)
    {
        while(j != 0 && s[i] != s[j + 1]) j = fail(j);
        if(s[i] == s[j + 1]) ++j; fail(i) = j; dep[i] = dep[j] + 1;
    }
    for(int i=1; i<=n; i++)
        for(int k=1; k<=lg[dep[i]]; k++) fa[i][k] = fa[fa[i][k - 1]][k - 1];
    int Q; cin >> Q; for(int p,q; Q--; )
    {
        cin >> p >> q;
        cout << lca(fa[p][0],fa[q][0]) << '\n';
    }
    return 0;
}