LCP 算法（DP）

1 LCP：从开头连续匹配多长？

LCP 是 Longest Common Prefix 的缩写，意思是最长公共前缀。

例如，比较两个字符串：

1
2
3

第一个：a b c d e f
第二个：a b c x y z
        └─abc─┘

从开头开始，前三个字符依次相同，第四个字符不同，所以它们的最长公共前缀是 abc，LCP 长度为 3。

LCP 要求从两个字符串的开头开始，逐个比较相邻字符。遇到不同字符，或其中一个字符串结束，匹配就停止。

1.1 一个字符串中，为什么会出现两个起点？

后缀是从某个位置开始，一直到字符串末尾的部分。

对于同一个字符串 $s$，定义：

全文使用从 0 开始的下标，字符串长度记为 $n$。

以 ababa 为例：

1
2
3
4
5
6

下标：0 1 2 3 4
字符：a b a b a

从 0 开始的后缀：ababa
从 2 开始的后缀：aba
公共前缀：      aba

因此 $\operatorname{LCP}(0,2)=3$。第二个后缀先结束，不能继续匹配。

再看两个不同的起点组合：

2 为什么需要一次求出许多 LCP？

如果只查询一对后缀，直接逐个比较字符即可，最坏需要 $O(n)$ 时间。

但有些问题需要枚举所有起点对。共有 $O(n^2)$ 对起点，如果每一对都重新逐字符比较，最坏总时间就会达到 $O(n^3)$。例如字符串全是 a 时，每次匹配都可能很长。

重复工作在哪里？

比较 ababa 的后缀 s[0..] 和 s[2..] 时，第一对 a 相同。去掉这两个 a，接下来要做的工作，正是比较 s[1..] 和 s[3..]。

所以，不同起点对的比较过程可以共用结果。我们不必每次都把整段字符重新看一遍。

3 用二维 DP 计算 LCP

3.1 状态：固定两个开头

定义：

两个下标分别记录两个后缀的起点。这是一个二维状态。

为了表示后缀走到末尾的情况，再约定位置 $n$ 对应空后缀：

只要其中一个后缀已经为空，公共前缀长度就是 0。

3.2 转移：先比较第一对字符

当 $i<n$ 且 $j<n$ 时，分两种情况：

• $s[i]\ne s[j]$：第一对字符就不同，公共前缀长度为 0。
• $s[i]=s[j]$：这一对贡献长度 1，剩余部分的长度是 $lcp[i+1][j+1]$。

于是：

这里不需要在多个选择之间取最大值。两个起点已经固定，第一对字符能否匹配也已经确定；能够匹配，就继续比较下一对，不能匹配就停止。

为什么相等时恰好是 $1+lcp[i+1][j+1]$？去掉第一对相同字符后，任何公共前缀都变成后面两个后缀的公共前缀；反过来，给后面最长的公共前缀接回这一对字符，就得到了当前最长的公共前缀。

3.3 顺序：先算右下方，再算当前位置

状态依赖为：

放到表格里看，当前位置需要的是右下方的格子。因此可以让 $i$、$j$ 都从大到小枚举：

1
2
3
4
5
6
7
8
9

for (int i = n - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
        if (s[i] == s[j]) {
            lcp[i][j] = lcp[i + 1][j + 1] + 1;
        } else {
            lcp[i][j] = 0;
        }
    }
}

代码执行前，需要准备一个至少为 $(n+1)\times(n+1)$ 的数组，并将边界第 $n$ 行、第 $n$ 列置为 0。

这里两个循环都倒序，是为了直观体现依赖关系。实际上，只要保证第 $i+1$ 行已经算完，第 $i$ 行里的 $j$ 也可以正序枚举，因为转移没有依赖本行的其他格子。

3.4 手算 ababa

先沿着依赖链看 $lcp[0][2]$：

1
2
3
4

lcp[0][2]：a == a，需要 1 + lcp[1][3]
lcp[1][3]：b == b，需要 1 + lcp[2][4]
lcp[2][4]：a == a，需要 1 + lcp[3][5]
lcp[3][5]：第二个后缀为空，值为 0

实际填表时，顺序反过来：

完整表格如下，最后一行和最后一列是空后缀边界：

表格还有两个可以自查的性质：$lcp[i][j]=lcp[j][i]$，并且 $lcp[i][i]=n-i$。

共有 $O(n^2)$ 个状态，每个状态只比较一对字符、读取一个已知状态，所以时间为 $O(n^2)$，保存整张表的空间为 $O(n^2)$。

4 应用：ABC141 E 的不重叠重复子串

题目链接：[ atcoder abc141_e: Who Says a Pun?]

给定字符串，求一个最长的非空字符串，使它在原串中至少出现两次，而且选出的两次出现不能重叠。不存在时，答案为 0。

注意答案是重复部分本身的长度。例如 abcabc 的答案是 3，对应两次 abc。

4.1 先固定两个起点

设两次出现的起点为 $i,j$，且 $i<j$，共同长度为 $len$。

第一条限制是两个子串相等。它们必须在从 $i,j$ 开始的公共前缀内，因此：

第二条限制是不能重叠。第一个子串占据 $[i,i+len-1]$，第二个从 $j$ 开始，因此：

将两个上界合在一起，固定这对起点时的最大合法长度就是：

这个值不仅是上界，也一定可以取到：它没有超过公共前缀长度，所以两段相等；它没有超过起点距离，所以两段不重叠。值为 0 时，表示这对起点无法提供非空答案。

最后枚举全部起点对：

4.2 为什么 ababa 的答案不是 3？

对于 $i=0,j=2$，有 $lcp[0][2]=3$，但两个长度为 3 的 aba 占据的区间分别是 $[0,2]$ 和 $[2,4]$，共用了位置 2。

把长度限制为 2，则两个 ab 占据 $[0,1]$ 和 $[2,3]$，不再重叠。

LCP 负责限制“能够相等多长”，起点距离负责限制“多长才不会重叠”。两个限制都必须保留。

4.3 完整 C++17 代码

先计算完整 LCP 表，再枚举起点对，代码中的两个步骤分别对应上面的两个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5005;
// 全局数组自动初始化为 0，第 n 行和第 n 列表示空后缀。
int lcp[maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    // lcp[i][j]：从 i、j 开始的两个后缀的最长公共前缀长度。
    // 当前状态依赖右下方的 lcp[i + 1][j + 1]，因此从后向前计算。
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (s[i] == s[j]) {
                lcp[i][j] = lcp[i + 1][j + 1] + 1;
            } else {
                lcp[i][j] = 0;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 相等限制长度不超过 lcp[i][j]，不重叠限制长度不超过 j - i。
            int len = min(lcp[i][j], j - i);
            ans = max(ans, len);
        }
    }

    cout << ans << '\n';
    return 0;
}

官方样例：

1
2
3
4
5
6

输入：
5
ababa

输出：
2

另外两个官方样例 xy、strangeorange 的答案分别为 0、5。后者的两个 range 分别从位置 2 和 8 开始。

题目限制为 $n\le 5000$、内存限制为 1024 MiB。代码将 lcp 放在全局，避免把大型二维数组放进栈；全局数组也会自动初始化为 0。

按每个 int 占 4 字节计算，5005 × 5005 的数组约占 100.2 MB，即 95.6 MiB，符合本题内存限制。

填表和枚举起点对都需要 $O(n^2)$ 时间，总时间仍为 $O(n^2)$，额外空间为 $O(n^2)$。换到内存限制更小的题目时，需要重新评估能否保存整张表。

5 和连续段 DP 有什么关系？

前一篇 [ Rbook: 连续段 DP：为什么要以当前位置结尾] 讲过：固定距离 $d$，比较 $s[i]$ 与 $s[i+d]$，再统计连续匹配的字符对。

ABC141 E 也能这样做。这里没有问号，两个字符必须直接相等。

5.1 固定距离，就是沿着 LCP 表的一条对角线

固定 $d=j-i$ 后，比较的字符对依次为：

这些位置对在二维表中，恰好位于同一条从左上到右下的对角线上。

以 ababa、$d=2$ 为例，三对字符都相等：

它们描述的是同一段匹配关系，但状态的端点不同：

• 连续计数固定的是结尾，所以依赖前一对，扫描时向前累加。
• LCP 固定的是开头，所以依赖后一对，填表时从后向前累加。

不要把同一位置的 cnt 和 lcp[i][i+d] 当成同一个值。例如表中 $i=0$ 时，前者为 1，后者为 3。

5.2 连续匹配对数如何变成不重叠答案？

设扫描到左侧位置 $i$ 时，连续匹配对数为 cnt。若从这段末尾取出 $k$ 对，则两段相同子串占据：

它们不重叠，要求第一段的结尾在第二段的起点之前，即：

同时，能够取出的字符对数不能超过 cnt，所以当前可以提供的最大合法长度为：

枚举所有距离，并扫描该距离下的全部位置，就覆盖了所有可能的子串对。对于任意一对长度为 $k$ 的合法相同子串，设其起点为 $l,l+d$；扫描到 $i=l+k-1$ 时，连续匹配对数至少为 $k$，且不重叠保证 $k\le d$，因此不会漏掉它。

对应的完整实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    int ans = 0;
    for (int d = 1; d < n; d++) {
        int cnt = 0;  // 当前距离下，以位置 i 结尾的连续匹配对数。
        for (int i = 0; i + d < n; i++) {
            if (s[i] == s[i + d]) {
                cnt++;
            } else {
                cnt = 0;
            }
            // 取当前匹配段末尾的 len 对，不重叠要求 len <= d。
            int len = min(cnt, d);
            ans = max(ans, len);
        }
    }

    cout << ans << '\n';
    return 0;
}

注意这里的 $d$ 要枚举到 $n-1$。两次出现可以相隔很远，中间允许有空隙。例如 abcxabc 的两次 abc 相距 4，虽然答案长度只有 3，仍然需要检查 $d=4$。

二维 LCP 表可以保留任意起点对的查询结果；固定距离计数在本题中只需维护全局答案，因此不必保存整张表。

5.3 与 CF1948D 的条件有什么区别？

两道题都可以固定距离、统计连续匹配，但对匹配段的要求不同。

因此，CF1948D 中“达到 $d$ 就返回 $2d$”的代码不能直接搬到本题。应该先检查两题中“相邻”“不重叠”以及“答案长度”的具体含义。

6 三个自查练习

6.1 练习一：LCP 很长，合法长度也一定很长吗？

设 s = "aaaaaa"，分别计算起点对 $(0,1)$ 和 $(0,3)$ 的 LCP 长度与最大不重叠长度。本题的全局答案是多少？

6.2 练习二：为什么遇到不相等的字符必须归零？

设 s = "xabzab"。虽然两个起点后面都出现了 ab，为什么 $lcp[0][3]=0$？

6.3 练习三：只看当前匹配段的总长度够吗？

在 ababa 中固定 $d=2$，连续匹配了 3 对字符。为什么只能贡献长度为 2 的答案，而不能贡献 3？

7 进一步阅读

本文计算的是所有后缀对的 LCP，使用二维 DP 即可完成。后缀数组相关资料中的“LCP 数组”通常只保存按字典序排列后相邻后缀的 LCP，数据的组织方式与这里的二维表不同。

现阶段先掌握状态含义、逆序依赖和不重叠约束即可。本题不需要后缀数组、字符串哈希或 KMP。

• ABC141 E 原题
• AtCoder 题解：用二维 DP 求所有后缀对的 LCP