P3426

cosf · 2026-08-05 14:32:24 · 题解

一篇有严格证明的题解。

称原题中的关系为“A 可被 B 表示”，即可以用若干个 B 拼出 A。

观察到几个重要的性质：

• 若 A 可以被 B 表示，则 B 为 A 的 border。

  考虑 B 表示 A 的第一个串和最后一个串，分别为 A 的前缀、后缀，符合 border 的定义。

• 设 S 的两个 border 为 \lvert s_1 \rvert \lt \lvert s_2 \rvert。若 S 可被 s_1 表示，则 s_2 也能被 s_1 表示。

  任取一个 s_1 表示 S 的方案。我们能够在其中找到一段长度 \in [\max(\lvert s_1 \rvert, \lvert s_2 \rvert - \lvert s_1 \rvert), \lvert s_2\rvert] 的前缀，使得其能被 s_1 表示。同理，可以找到长度 \in [\max(\lvert s_1 \rvert, \lvert s_2 \rvert - \lvert s_1 \rvert), \lvert s_2\rvert] 的 S 的后缀，（因为 s_1, s_2, S 互为 border，）这个后缀也是 s_2 的后缀。那么这两段总长度 \ge \lvert s_2 \rvert，拼在一起（中间可能有重叠部分）就是 s_1 表示 s_2 的方案。

• 若 S 能被 s_1,s_2 表示，设 \lvert s_1 \rvert \lt \lvert s_2 \rvert，则 s_1 是 s_2 的 border。

  前两条性质的直接推论。

下文用前缀的长度代表前缀本身。

回到原题。设 f_i 表示前缀 i 的答案，即最短能表示 S_{[1, i]} 的串的长度。设 \pi_i 表示 i 的最长 border（即 KMP 中求出来的失配指针）。则我们可以说明 f_i \in \{i, f_{\pi_i}\}。

显然若 f_i \ne i，则 f_i \le \pi_i。并且，由第二个性质，f_i \ge f_{\pi_i}。我们可以说明此时必有 f_i = f_{\pi_i}。

若 f_i \ne f_{\pi_i}，则 f_i \in (f_{\pi_i}, \pi_i]。由 border 的树性得到 f_i 是 \pi_i 的 border。仍由性质 2 得 f_i 可被 f_{\pi_i} 表示，必然不是最小值。因此性质得证。

不过我们还需要判断 f_{\pi_i} 是否能表示 i。它最后一次覆盖的位置是 S_{[i - f_{\pi_i} + 1, i]}，因此一个充分条件是 \exists j \in [i - f_{\pi_i}, i], f_j = f_{\pi_i}。我们能说明这也是必要的。

假设存在一个覆盖到 j \in [i - f_{\pi_i}, i] 的解（即 f_{\pi_i} 能表示 j），我们能说明 f_j = f_{\pi_i}。首先肯定有 f_j \le f_{\pi_i}。另一方面，由第三个性质，f_j 是 f_{\pi_i} 的 border，由第二个性质知 f_{\pi_i} 能被 f_j 表示，进而推出 \pi_i 能被 f_j 表示，所以 f_{\pi_i} \le f_j（这个不等式是从 f 本身的定义出发的，而这句话前面别的 f_{\pi_i} 是将 f_{\pi_i} 视作一个已知的定值），这两个数只能相等。

最后求答案是容易的。只需要对每个值 f 维护最大的下标 i 就行了，复杂度线性。

#include <iostream>
using namespace std;

#define MAXN 500005

string S;
int n;

int pi[MAXN], f[MAXN], las[MAXN];

int main() {
    cin >> S;
    n = S.size();
    f[0] = 1;
    for (int i = 1; i < n; i++) {
        pi[i] = pi[i - 1];
        while (pi[i] && S[i] != S[pi[i]]) pi[i] = pi[pi[i] - 1];
        if (S[i] == S[pi[i]]) pi[i]++;
        if (pi[i] && las[f[pi[i] - 1]] >= i - pi[i]) f[i] = f[pi[i] - 1];
        else f[i] = i + 1;
        las[f[i]] = i;
    }
    cout << f[n - 1] << '\n';
    return 0;
}