CF1446B.Catching Cheaters

You are given two strings $A$ and $B$ representing essays of two students who are suspected cheaters. For any two strings $C$, $D$ we define their similarity score $S(C,D)$ as $4\cdot LCS(C,D) - |C| - |D|$, where $LCS(C,D)$ denotes the length of the Longest Common Subsequence of strings $C$ and $D$.

You believe that only some part of the essays could have been copied, therefore you're interested in their substrings.

Calculate the maximal similarity score over all pairs of substrings. More formally, output maximal $S(C, D)$ over all pairs $(C, D)$, where $C$ is some substring of $A$, and $D$ is some substring of $B$.

If $X$ is a string, $|X|$ denotes its length.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters.

Pay attention to the difference between the substring and subsequence, as they both appear in the problem statement.

You may wish to read the Wikipedia page about the Longest Common Subsequence problem.

给你两个字符串 $A$ 和 $B$，分别代表两名涉嫌抄袭的学生所写的作文。对于任意两个字符串 $C$、$D$，我们定义它们的相似度得分 $S(C,D)$ 为 $4\cdot LCS(C,D) - |C| - |D|$，其中 $LCS(C,D)$ 表示字符串 $C$ 与 $D$ 的最长公共子序列（Longest Common Subsequence）的长度。

你认为可能仅有作文的某一部分被抄袭，因此你关注的是它们的子串（substring）。

请计算所有子串对的相似度得分的最大值。更准确地说，输出所有满足条件的字符串对 $(C, D)$ 中 $S(C, D)$ 的最大值，其中 $C$ 是 $A$ 的某个子串，$D$ 是 $B$ 的某个子串。

若 $X$ 是一个字符串，则 $|X|$ 表示其长度。

若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零个或全部）字符，并从结尾删除若干（可能为零个或全部）字符而得到，则称 $a$ 是 $b$ 的子串（substring）。

若字符串 $a$ 可通过从字符串 $b$ 中删除若干（可能为零个或全部）字符而得到，则称 $a$ 是 $b$ 的子序列（subsequence）。

请注意“子串”与“子序列”的区别，因为本题中两者均会出现。

你或许希望阅读关于最长公共子序列问题的 Wikipedia 页面。

The first line contains two positive integers $n$ and $m$ ($1 \leq n, m \leq 5000$) — lengths of the two strings $A$ and $B$.

The second line contains a string consisting of $n$ lowercase Latin letters — string $A$.

The third line contains a string consisting of $m$ lowercase Latin letters — string $B$.

第一行包含两个正整数 $n$ 和 $m$（$1 \leq n, m \leq 5000$）—— 分别为字符串 $A$ 和 $B$ 的长度。

第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 —— 字符串 $A$。

第三行包含一个由 $m$ 个小写拉丁字母组成的字符串 —— 字符串 $B$。

Output maximal $S(C, D)$ over all pairs $(C, D)$, where $C$ is some substring of $A$, and $D$ is some substring of $B$.

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

For the first case:

abb from the first string and abab from the second string have LCS equal to abb.

The result is $S(abb, abab) = (4 \cdot |abb|$) - $|abb|$ - $|abab|$ = $4 \cdot 3 - 3 - 4 = 5$.

对于第一种情况：

第一个字符串中的 abb 和第二个字符串中的 abab 的最长公共子序列（LCS）等于 abb。

结果为 $S(abb, abab) = (4 \cdot |abb|)$ - $|abb|$ - $|abab|$ = $4 \cdot 3 - 3 - 4 = 5$。