洛谷 P5829 题解

admin 2021-07-09 AM 114℃ 0条

题目链接

分析

首先 KMP 求 $fail$。

则有 $\bold{Border}(s_1s_2\ldots s_i)=fail_i\bigcup\bold{Border}(s_1s_2\ldots s_{fail_i})$。

建立一棵树,使得 $fa_i=fail_i$,那么 $\bold{Border}(s_1s_2\ldots s_i)$ 就是这棵树上 $i$ 的所有祖先(不包括自己)。

查询 $p$ 前缀和 $q$ 前缀,就是查找这棵树上 $fa_p$ 和 $fa_q$ 的 LCA。

这棵树就是失配树

解决

这里倍增貌似比较好写,因为可以直接知道 $fa_i$。

其他题解没有提到的一点:

其他题解里面求的是 $p$ 和 $q$ 的 LCA,而不是 $fa_p$ 和 $fa_q$ 的 LCA。但是 $x \not \in \bold{Border}(s_1s_2\ldots s_x)$,所以需要稍微修改倍增找 LCA 的。其他题解说是 “正常的倍增求 LCA”,其实是不对的。

正常的倍增求 LCA 中,要在将 $x$ 和 $y$ 跳到同一层之后判断 $x$ 和 $y$ 是否相等,如果相等就返回 $x$,但是在本题中不应该判,因为如果 $x=y$,说明 $x$ 是 $y$ 的祖先或者 $y$ 是 $x$ 的祖先,,所以仍然应该返回 $fa_x$。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e6 + 5, Log = 20;
int n, m, fail[N], dep[N], fa[N][Log];
char ch[N];

void getFail()
{
    fail[1] = 0;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j > 0 && ch[i] != ch[j + 1])
            j = fail[j];
        if (ch[i] == ch[j + 1])
            j++;
        fail[i] = j;
    }
}

void prework()
{
    getFail();
    for (int i = 1; i <= n; i++)
    {
        dep[i] = dep[fail[i]] + 1, fa[i][0] = fail[i];
        for (int j = 1; j < Log; j++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
}

int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = Log - 1; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    for (int i = Log - 1; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

void read(int &ret)
{
    ret = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
}

int main()
{
    scanf("%s", ch + 1);
    n = strlen(ch + 1);
    prework();
    read(m);
    while (m--)
    {
        int x, y;
        read(x), read(y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}
标签: 字符串, KMP

非特殊说明,本博所有文章均为博主原创。

评论啦~