洛谷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;
}