洛谷P1117 [NOI2016] 优秀的拆分题解

题目链接：P1117 [NOI2016] 优秀的拆分

题意：

如果一个字符串可以被拆分为 $\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$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。

在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。

字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$，表示数据的组数。

接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。

输出格式

输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

数据范围：

对于95%的测试点， $1 \le T \le 10,~1 \le \sum |S_i| \le 2000$ 。

对于全部的测试点，保证 $1 \le T \le 10,~1 \le \sum |S_i| \le 3\times 10^4$ 。

注意到 $\rm AABB$ 的串就是由两个 $\rm AA$ 的串拼成的。

设 $f_i$ 为以 $i$ 结尾的 AA 串个数，$g_i$ 为以 $i$ 开头的 AA 串个数，则

$\mathrm{Ans} = \sum_{i=1}^nf_i \cdot g_{i+1}$

用字符串哈希可以 $\mathcal{O}(n^2)$ 解决，直接爽拿 95pts 。

考虑优化。枚举 A 的长度 $\rm len$ ，并标记所有为 $\rm len$ 的倍数的点，不妨称这些点为「关键点」。

因为一个 AA 串必然经过两个关键点，所以我们可以考察相邻两个关键点 $i,j$ 的贡献。

则当 $\operatorname{lcp}(\operatorname{suf}i,\, \operatorname{suf}j) + \operatorname{lcs}(\operatorname{pre} (i-1),\,\operatorname{pre} (j-1)) < \mathrm{len}$ 时，一定不能构成 AA 串。（如图）

$\cdots\underbrace{\cdots\,i-1}_{\rm lcs},\, \overbrace{ \overbrace{ \underbrace{i\,\cdots\cdots\cdots}_{\rm lcp}\cdots\cdots \underbrace{\cdots\, j-1}_{\rm lcs} }^{\rm len},\, \underbrace{ \underbrace{j\,\cdots\cdots\cdots}_{\rm lcp}\cdots\cdots }_{\operatorname{suf} j} }^{\operatorname{suf} i}$

反之两者的会有交集，而 A 的末端可以位于 $\mathrm{lcp} + \mathrm{lcs} - \mathrm{len} + 1$ 个位置上（包括交集左端一位）

由于这是一个区间，我们可以直接在 $f,g$ 上做差分。

现在的问题就是如何求出两个后缀的 $\rm lcp$ 了（以及前缀的 $\rm lcs$），考虑正反构建后缀数组。

记 $\operatorname{LCP}(i,j)$ 为排名 $i$ 和排名 $j$ 的后缀的 lcp，显然 $\operatorname{lcp}(\operatorname{suf}i,\, \operatorname{suf}j) = \operatorname{LCP}(\operatorname{rk} i, \,\operatorname{rk} j)$ 。

根据 LCP 的性质以及后缀数组 height 数组的性质（参考这篇）可知

$\operatorname{LCP}(\operatorname{rk} i, \,\operatorname{rk} j) = \min_{\operatorname{rk} (i+1) \le k \le \operatorname{rk} j} \{\operatorname{height} k\}$

这就是一个不带修改的区间 min 查询，考虑用 ST 表维护。

时间复杂度 $\mathcal{O}(Tn \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(3e4 + 15))
#define mem(a) memset(a, 0, sizeof(a))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N]; int lg[N];
struct SA
{
    int sa[N], rk[N * 2], tmp[N * 2], cnt[N], height[N], st[16][N];
    void sort(const int n, const int m, int w)
    {
        memset(cnt, 0, (m + 5) * sizeof(int));
        for(int i = 1; i <= n; i++) tmp[i] = sa[i];
        for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
        for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
    }
    void build(const int n)
    {
        mem(sa); mem(rk); mem(tmp);
        const int m = max(n, 233);
        for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
        for(int w = 1; w < n; w <<= 1)
        {
            sort(n, m, w); sort(n, m, 0);
            for(int i = 1; i <= n; i++) tmp[i] = rk[i];
            for(int i = 1, p = 0; i <= n; i++)
                if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
        }
    }
    void getheight(const int n)
    {
        int k = 0;
        for(int i = 1; i <= n; height[rk[i]] = k, i++)
        {
            const int j = sa[rk[i] - 1]; if(k) --k;
            while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
        }
    }
    void buildSA(const int n) { build(n); getheight(n); }
    void buildST(const int n)
    {
        for(int i = 1; i <= n; i++) st[0][i] = height[i];
        for(int i = 1; i < 16; i++)
        {
            int *f = st[i], *g = st[i - 1];
            for(int j = 1; j + (1 << i) - 1 <= n; j++)
                f[j] = min(g[j], g[j + (1 << (i - 1))]);
        }
    }
    int query(int L, int R)
    {
        int l = min(rk[L], rk[R]) + 1, r = max(rk[L], rk[R]);
        int k = lg[r - l + 1];
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
} a, b;
int f[N], g[N];
void solve()
{
    cin >> (s + 1); mem(f); mem(g);
    int n = strlen(s + 1); a.buildSA(n); a.buildST(n);
    reverse(s + 1, s + 1 + n); b.buildSA(n); b.buildST(n);
    for(int len = 1; len * 2 <= n; len++)
        for(int i = len, j = i + len; j <= n; i += len, j += len)
        {
            const int lcp = min(a.query(i, j), len);
            const int lcs = min(b.query(n - i + 2, n - j + 2), len - 1);
            const int t = lcp + lcs - len + 1;
            if(lcp + lcs >= len)
            {
                ++f[j + lcp - t]; --f[j + lcp];
                ++g[i - lcs]; --g[i - lcs + t];
            }
        }
    for(int i = 1; i <= n; i++) { f[i] += f[i - 1], g[i] += g[i - 1]; }
    ll res = 0;
    for(int i = 1; i < n; i++) res += (ll)f[i] * g[i + 1];
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(int i = 2; i <= N - 5; i++) lg[i] = lg[i >> 1] + 1;
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/article/v32wnt6z

补充：（也可以算题外话）

上面插图的源码

\cdots\underbrace{\cdots\,i-1}_{\rm lcs},\,
\overbrace{
	\overbrace{
		\underbrace{i\,\cdots\cdots\cdots}_{\rm lcp}\cdots\cdots
		\underbrace{\cdots\, j-1}_{\rm lcs}
	}^{\rm len},\,
	\underbrace{
		\underbrace{j\,\cdots\cdots\cdots}_{\rm lcp}\cdots\cdots
	}_{\operatorname{suf} j}
}^{\operatorname{suf} i}