「NOI 2016」优秀的拆分

题目链接:UOJ 219

如果一个字符串可以被拆分为 $\text{AABB}​$ 的形式,其中 $\text{A}​$ 和 $\text{B}​$ 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。

例如,对于字符串 $ \texttt{aabaabaa} ​$ ,如果令 $\text{A}=\texttt{aab}​$,$\text{B}=\texttt{a}​$,我们就找到了这个字符串拆分成 $\text{AABB}​$ 的一种方式。

一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。

比如我们令 $\text{A}=\texttt{a}$,$\text{B}=\texttt{baa}$,也可以用 $\text{AABB}$ 表示出上述字符串;但是,字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  1. 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  2. 在一个拆分中,允许出现 $\text{A}=\text{B}​$。例如 $\texttt{cccc}​$ 存在拆分 $\text{A}=\text{B}=\texttt{c}​$。
  3. 字符串本身也是它的一个子串。

本题有 $T​$ 组数据。

数据范围:$1 \le T \le 10$,$1 \le n \le 3 \times 10 ^ 4$。


Solution

由于在 $\text{AABB}$ 中,前面的 $\text{AA}$ 和后面的 $\text{BB}$ 是两个独立的部分,其形式均为 $\text{AA}$。那么我们分别考虑这些贡献,最后统计答案。

设 $f(i), g(i)$ 分别 表示第 $i$ 个位置往前、往后分别有多少个形如 $\text{AA}$ 的子串。那么答案为:

$$ \sum_{i = 1} ^ {n - 1} f(i) \cdot g(i +1) $$

现在的问题就是如何求 $f(i), g(i)$。考虑一种最暴力的方法:枚举位置,枚举往前、往后的子串。通过 $\text{Hash}$ 显然可以得到一种 $\mathcal O(n ^ 2)$ 的做法。

考虑如何优化。我们使用一种数论中常用的手法:变换枚举顺序,先枚举长度,再计算哪些位置会产生贡献。

假设当前枚举的 $\text{AA}$ 的长度为 $2L$,我们以 $L$ 为步长放置关键点(也就是在 $L, 2L, 3L, \dots $ 放置关键点),可以发现,对于任意一个长度为 $2L$ 的子串,必定会覆盖 $2$ 个关键点。因此可以枚举相邻两个关键点 $i, j$,求出 $\text{prefix}(i), \text{prefix}(j)$ 的 $\text{LCS} = x$ 和 $\text{suffix}(i), \text{suffix}(j)$ 的 $\text{LCP} = y$。可以通过后缀数组求得。

接下来的内容需要读者自己画图理解。当 $x + y - 1 < L$ 时,可以证明长度为 $2L$ 的 $\text{AA}$ 子串不可能经过 $i, j$ 两点。否则会产生贡献的点是一段区间,直接差分统计贡献。

由于枚举长度和关键点的复杂度为调和级数,因此单次询问复杂度为 $\mathcal O(n \log n)$。

时间复杂度:$\mathcal O(T \cdot n \log n)$


Code

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

const int N = 3e4 + 5;

int T, n, f[N], g[N];
char s[N];

template <int MAX>
struct SuffixArray {
    static const int N = MAX, logN = 15;
    int n, m, sa[N], rk[N], cnt[N], tmp[N], height[N], lg[N], f[N][logN];
    void radixSort() {
        std::fill(cnt + 1, cnt + m + 1, 0);
        for (int i = 1; i <= n; i++) cnt[rk[i]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
    }
    template <typename Tp>
    void build(Tp *a, int _n, int _m) {
        n = _n, m = _m;
        for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
        radixSort();
        for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
            p = 0;
            for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
            radixSort();
            std::swap(rk, tmp);
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++) {
                int u = sa[i - 1], v = sa[i];
                int uu = (u + l <= n ? u + l : 0), vv = (v + l <= n ? v + l : 0);
                rk[sa[i]] = (tmp[u] == tmp[v] && tmp[uu] == tmp[vv] ? p : ++p);
            }
        }
        a[n + 1] = 0;
        for (int i = 1, k = 0; i <= n; i++) {
            k -= (k > 0);
            int j = sa[rk[i] - 1];
            for (; a[i + k] == a[j + k]; k++);
            height[rk[i]] = k;
        }
    }
    void buildRMQ() {
        for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= n; i++) f[i][0] = height[i];
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int query(int l, int r) {
        int k = lg[r - l + 1];
        return std::min(f[l][k], f[r - (1 << k) + 1][k]);
    }
    int lcp(int i, int j) {
        i = rk[i], j = rk[j];
        if (i == j) return n - sa[i] + 1;
        if (i > j) std::swap(i, j);
        return query(i + 1, j);
    }
};

SuffixArray<N> S1, S2;

int lcp(int i, int j) {
    return S1.lcp(i, j);
}
int lcs(int i, int j) {
    return S2.lcp(n - i + 1, n - j + 1);
}
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        S1.build(s, n, 255), S1.buildRMQ();
        std::reverse(s + 1, s + n + 1);
        S2.build(s, n, 255), S2.buildRMQ();
        std::fill(f + 1, f + n + 1, 0);
        std::fill(g + 1, g + n + 1, 0);
        for (int l = 1; l <= (n >> 1); l++) {
            for (int i = l, j = l + l; j <= n; i += l, j += l) {
                int x = std::min(lcs(i, j), l), y = std::min(lcp(i, j), l);
                if (x + y - 1 < l) continue;
                f[j + l - x]++, f[j + y]--;
                g[i - x + 1]++, g[i + y - l + 1]--;
            }
        }
        for (int i = 1; i <= n; i++) {
            f[i] += f[i - 1], g[i] += g[i - 1];
        }
        long long ans = 0;
        for (int i = 1; i < n; i++) ans += 1LL * f[i] * g[i + 1];
        printf("%lld\n", ans);
    }
    return 0;
}

发表评论