CF1446B Catching Cheaters

给定两个字符串 $A$ 和 $B$，它们分别代表两名被怀疑作弊的学生的作文。对于任意两个字符串 $C$ 和 $D$，我们定义它们的相似度分数 $S(C, D)$ 为 $4\cdot LCS(C, D) - |C| - |D|$，其中 $LCS(C, D)$ 表示字符串 $C$ 和 $D$ 的最长公共子序列的长度。 你认为只有作文中的某些部分可能被抄袭，因此你只关心它们的子串。 请计算所有子串对中最大的相似度分数。更正式地说，输出所有 $(C, D)$ 对中最大的 $S(C, D)$，其中 $C$ 是 $A$ 的某个子串，$D$ 是 $B$ 的某个子串。 如果 $X$ 是一个字符串，$|X|$ 表示其长度。 字符串 $a$ 是字符串 $b$ 的子串，指的是 $a$ 可以通过从 $b$ 的开头和结尾各删除若干（可能为零或全部）字符得到。 字符串 $a$ 是字符串 $b$ 的子序列，指的是 $a$ 可以通过从 $b$ 中删除若干（可能为零或全部）字符得到。 请注意子串和子序列的区别，它们在题目中均有出现。 你可以参考[最长公共子序列问题的维基百科页面](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)。

第一行包含两个正整数 $n$ 和 $m$（$1 \leq n, m \leq 5000$），分别表示两个字符串 $A$ 和 $B$ 的长度。 第二行包含一个由 $n$ 个小写拉丁字母组成的字符串，表示字符串 $A$。 第三行包含一个由 $m$ 个小写拉丁字母组成的字符串，表示字符串 $B$。

输出所有 $(C, D)$ 对中最大的 $S(C, D)$，其中 $C$ 是 $A$ 的某个子串，$D$ 是 $B$ 的某个子串。

对于第一个样例： 第一个字符串中的 abb 和第二个字符串中的 abab 的 LCS 等于 abb。 结果为 $S(abb, abab) = (4 \cdot |abb|) - |abb| - |abab| = 4 \cdot 3 - 3 - 4 = 5$。 由 ChatGPT 4.1 翻译