LG5829 【模板】失配树 题解

Tag

字符串，最近公共祖先。

Description

给定一个字符串 \(S\)，一共 \(m\) 次询问，每一次询问字符串 \(S\) 的前缀 \(p\) 与前缀 \(q\) 的最长公共 border。
\(\texttt{data range:} |S| \leq 10^6, m \leq 10^5\).

Solution

有一个非常显然的结论，就是一个字符串的 border 一定包含了比其短的所有该字符串的 border。

对于找出一个字符串的 border 我们有非常优秀的 KMP 算法可以做到线性的时间复杂度求出一个单字符串的所有前缀的最长 border。

由于我们要求最长公共 border，所以直观的感受一下将失配指针看成当前点的父亲节点，然后形成的一颗树就是整个字符串的失配树，我们要做的就是查询两个点的最近公共祖先就可以了。

还有一个性质就是所有点的父亲节点一定小于当前节点，所以我们无需建树，可以线性的预处理，\(O(\lg n)\) 的查询两个节点的最近公共祖先，用树剖即可。

Code

constexpr int N = 1e6 + 10;

char s[N];

int fa[N], son[N], top[N], sz[N], dep[N];
int lca(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

void solve() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 2, j = 0; i <= n; i++) {
        while(j && s[j + 1] != s[i]) j = fa[j];
        if(s[i] == s[j + 1]) j++;
        fa[i] = j;
    }// KMP 过程
    ROF(i, n, 1) {
        sz[i]++;
        if(fa[i]) sz[fa[i]] += sz[i];
        if(sz[i] >= sz[son[fa[i]]]) son[fa[i]] = i;
    }
    FOR(i, 1, n) {
        dep[i] = dep[fa[i]] + 1;
        if(son[fa[i]] != i) top[i] = i;
        else top[i] = top[fa[i]];
    }// 树剖预处理
    int q = rd;
    while(q--) {
        int x = fa[rd], y = fa[rd];
        cout << lca(x, y) << '\n';
    }
    return ;
}

Final

树剖的常数大概是倍增 lca 常数的 \(\frac 23\) 左右，而且预处理的时间和空间复杂度都是线性的，非常优秀，开了 O2 之后是最优解第一面除了一帮子写取模跳父亲的人之外的最快的了。

细节：由于一个前缀的 border 不能是他自己，所以一定要先往自己的父亲跳一下。

安利：希望大家多写树剖 lca 不要写倍增 lca，阿里嘎多。