P4081 题解

· · 题解

前言

貌似这题的后缀数组题解较少，排名第一的后缀数组题解排版炸了，排第二的太复杂了，所以我来贡献一篇题解。

前置知识

思路

首先观察题目，抽象题意如下：

给定 n 个串，求出每个串不出现在其他串中的本质不同子串数量。

我们想起我们曾经学过的后缀数组求本质不同的子串数量，与这题十分相仿。所以我们可以尝试模仿这种思路。

首先把这 n 个串首尾相接，中间加上各不相同的分隔符，防止出现横跨不同串的最长公共前缀，这是后缀数组处理多个串的常用思路。

对于每个后缀，我们可以求出它所在原串的编号，设 id[i] 表示第 i 个后缀所在的原串。

按 sa 的顺序从前往后枚举每一个后缀，新增的子串就是当前后缀除去与上一个 id 相同的后缀的 lcp 后剩下的前缀。当然我们还要排除掉和其他 id 不同的后缀的 lcp，于是取一个 max 即可。

因此，对于每一个后缀 x，它排除的答案为 \max(lcp(x, i), lcp(x, j), lcp(x, k))，其中 i 是满足 rk[i] < rk[x],id[i]\neq id[x] 中排名最大的一个后缀，j 是满足 rk[j] > rk[x], id[j] \neq id[x] 中排名最小的后缀，k 是满足 id[k] = id[x] 中排名最大的后缀。

我们可以对于每一个 x 预处理出 lcp(x, i), lcp(x, j)，然后仿照后缀数组求本质不同子串数量的方式，将每个串的初始答案设为 \cfrac{len \times (len +1)} {2}，接着对于每个 i，让其对应串的答案减去应排除的答案即可。

代码实现

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>

using namespace std;

using LL = long long;
const int N = 4e5 + 10;

int n, m;
int sa[N], rk[N], height[N], x[N], y[N], c[N];
int id[N], len[N];
int str[N]; char tmp[N];
int a[N], b[N];
int st[N][31], lg2[N];
int string_cnt;
LL ans[N];

void buildSA(void) // 后缀数组模板
{
    m = 400000;
    for (int i = 0; i <= m; ++i) c[i] = 0;
    for (int i = 1; i <= n; ++i) ++c[x[i] = str[i]];
    for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; ++i)
            y[++num] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > k) y[++num] = sa[i] - k;
        for (int i = 0; i <= m; ++i) c[i] = 0;
        for (int i = 1; i <= n; ++i) ++c[x[i]];
        for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
        for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = num = 1;
        for (int i = 2; i <= n; ++i) {
            int ynow = sa[i] + k <= n ? y[sa[i] + k] : 0;
            int ynex = sa[i - 1] + k <= n ? y[sa[i - 1] + k] : 0;
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && ynow == ynex) ? num : ++num;
        }
        if (num == n) break;
        m = num;
    }

    for (int i = 1; i <= n; ++i)
        rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; ++i) {
        if (rk[i] == 1) continue;
        if (k) --k;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && str[i + k] == str[j + k])
            ++k;
        height[rk[i]] = k;
    }
}
void buildST(void)// ST 表模板
{
    for (int i = 2; i <= n; ++i)
        lg2[i] = lg2[i >> 1] + 1;
    for (int i = 1; i <= n; ++i)
        st[i][0] = height[i];
    for (int k = 1; k <= 30; ++k)
        for (int i = 1; i + (1 << k - 1) <= n; ++i)
            st[i][k] = min(st[i][k - 1], st[i + (1 << k - 1)][k - 1]);
}
int queryHeight(int l, int r) // ST 表查询操作
{
    ++l; int t = lg2[r - l + 1];
    return min(st[l][t], st[r - (1 << t) + 1][t]);
}

int main(void)
{
    scanf("%d", &string_cnt);
    for (int i = 1; i <= string_cnt; ++i) {
        scanf("%s", tmp + 1);
        for (len[i] = 1; tmp[len[i]]; ++len[i])
            str[++n] = tmp[len[i]], id[n] = i;
        str[++n] = 'z' + i;
        --len[i];
        ans[i] = 1ll * len[i] * (len[i] + 1) / 2;
    }
    str[n--] = 0;

    buildSA();
    buildST();

    int last = 0, llast = 0;
    // 预处理出 a[x], a[x] 表示本文中的 lcp(x, j)
    for (int i = n; i >= 1; --i) {
        if (id[sa[i]] != id[sa[last]])
            llast = last;
        last = i;
        a[i] = llast <= i ? 0 : queryHeight(i, llast);
    }

    for (int i = 1; i <= n; ++i) {
        int tmp = max(a[i], height[i]); // 容易证明, height[x] 等于本文中的 max(lcp(x, i), lcp(x, k))
        ans[id[sa[i]]] -= tmp;
    }
    for (int i = 1; i <= string_cnt; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}