竞极 Ace

最长公共子段

最长公共子段

题意

给定长度分别为 nn、mm 的两个整数序列 aa、bb，求它们的最长公共连续子段的长度。

子段必须在两个序列中都连续，但起始位置可以不同。若没有相同元素，答案为 00。

例如：

a：1 2 3 2 4
b：0 2 3 2 5

最长的相同子段为 2 3 2，长度为 33。

状态与转移

前面处理一个序列时，常用“以当前位置结尾”定义状态。现在有两个序列，就同时固定它们的结尾。

设 dp[i][j]dp[i][j] 表示以 a[i]a[i] 和 b[j]b[j] 结尾的最长相同子段的长度。

  • 若 a[i]=b[j]a[i]=b[j]，可以接在以 a[i−1]a[i-1]、b[j−1]b[j-1] 结尾的相同子段后面，长度增加 11。
  • 若 a[i]≠b[j]a[i]\ne b[j]，不存在以这两个位置结尾的非空相同子段，长度为 00。
$$dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & a[i]=b[j],\\ 0, & a[i]\ne b[j]. \end{cases}$$

初始化第 00 行、第 00 列为 00，表示其中一个序列为空。答案为所有状态的最大值，而不是 dp[n][m]dp[n][m]，因为最长相同子段不一定在序列末尾。

不相等时必须置为 00，不能从 dp[i−1][j]dp[i-1][j] 或 dp[i][j−1]dp[i][j-1] 转移，否则就允许跳过元素，不再保证连续。

参考代码

输入第一行为 n,mn,m，接下来两行分别为序列 aa、bb；输出最长相同子段的长度。约定 1≤n,m≤20001\le n,m\le2000，∣a[i]∣,∣b[j]∣≤109|a[i]|,|b[j]|\le10^9。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2005;
int n, m, a[N], b[N], dp[N][N];

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int j = 1; j <= m; ++j) cin >> b[j];

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = 0;
            ans = max(ans, dp[i][j]);
        }
    }

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

全局数组默认初始化为 00。时间复杂度 O(nm)O(nm)，空间复杂度 O(nm)O(nm)。