← 返回题目列表

Codeforces · 1446/B

B. 抓骗子

中文机器翻译题面 查看原题

给你两个字符串 $$$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$$$ 的子序列。

注意子字符串和子序列之间的区别,因为它们都出现在问题陈述中。

您可能希望阅读有关最长公共子序列问题的维基百科页面。

输入

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

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

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

输出

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

示例

输入 #1

4 5
abba
babab

输出 #1

5

输入 #2

8 10
bbbbabab
bbbabaaaaa

输出 #2

12

输入 #3

7 7
uiibwws
qhtkxcn

输出 #3

0

注意

对于第一种情况:

第一个字符串中的 abb 和第二个字符串中的 abab 的 LCS 等于 abb。

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