T2-13 论文查重

题意理解

从字符串 $A$ 中选一个子串 $C$，从 $B$ 中选一个子串 $D$，最大化相似度得分：

$$S(C,D) = 4 \cdot LCS(C,D) - |C| - |D|$$

---

思路分析

关键观察： 如果固定 LCS 的匹配位置，为最大化得分，$C$ 和 $D$ 应该恰好覆盖这些匹配位置（最短子串）。

设 LCS 的匹配点在 $A$ 中是 $i_1 < i_2 < \cdots < i_k$，在 $B$ 中是 $j_1 < j_2 < \cdots < j_k$。

则 $|C| = i_k - i_1 + 1$，$|D| = j_k - j_1 + 1$。

得分可以分解为：第一个匹配贡献 $2$，之后每个匹配 $(i_t, j_t)$ 贡献 $4 - (i_t - i_{t-1}) - (j_t - j_{t-1})$。

设 $dp[i][j]$ 表示以 $(i, j)$ 为最后一个匹配点（$A[i] = B[j]$）时的最大得分。

状态转移（$A[i] = B[j]$ 时）：

$$dp[i][j] = \max(2, \max_{i'<i,j'<j}(dp[i'][j'] + 4 - (i-i') - (j-j')))$$

令 $g[i][j] = dp[i][j] + i + j$，则转移变为：

$$dp[i][j] = \max(2, \max_{i'<i,j'<j}(g[i'][j']) + 4 - i - j)$$

用前缀最大值优化，可以做到 $O(nm)$。

答案： 所有 $dp[i][j]$ 的最大值，若无匹配则为 $0$

---

参考代码

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

const int MAXN = 5005;  // 最大字符串长度
const int INF = 0x3f3f3f3f;

int n, m;              // 两个字符串的长度
char A[MAXN], B[MAXN]; // 两个字符串
int maxG[MAXN];        // maxG[j]表示所有i'<i中g[i'][j]的最大值
int newG[MAXN];        // 当前行的g值

int main() {
    cin >> n >> m;     // 读入字符串长度
    cin >> (A + 1) >> (B + 1);  // 读入字符串，下标从1开始
    
    for (int j = 0; j <= m; j++) {  // 初始化为负无穷
        maxG[j] = -INF;
    }
    
    int ans = 0;  // 答案，至少为0（可以选空子串）
    
    for (int i = 1; i <= n; i++) {  // 枚举A的每个位置
        for (int j = 0; j <= m; j++) {  // 初始化当前行的g值
            newG[j] = -INF;
        }
        
        int preMax = -INF;  // 前缀最大值，表示max(maxG[1..j-1])
        
        for (int j = 1; j <= m; j++) {  // 枚举B的每个位置
            if (A[i] == B[j]) {  // 当前位置可以匹配
                int dp = max(2, preMax + 4 - i - j);  // 状态转移
                ans = max(ans, dp);  // 更新答案
                newG[j] = dp + i + j;  // 记录当前的g值
            }
            preMax = max(preMax, maxG[j]);  // 更新前缀最大值
        }
        
        for (int j = 1; j <= m; j++) {  // 更新maxG数组
            maxG[j] = max(maxG[j], newG[j]);
        }
    }
    
    cout << ans << endl;  // 输出答案
    return 0;
}