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