19. Teacher Panda and plagiarism

单点时限: 4.0 sec

内存限制: 256 MB

英语作文的 Online Judge 真不是什么靠谱的系统,它有的时候连文章是否是抄袭也分不出来。So sad!

熊猫老师,ECNU 英语教师,对此事表示非常生气。在周一的英语课上,他大发雷霆,谈论抄袭的弊端。他甚至对抄袭行为进行了分类:

  • 相似度大于 ,认定为抄袭 (COPY);
  • 相似度大于 ,认定为剽窃 (PLAGIARISM);
  • 相似度为 ,认定为「谋杀」(MURDER)。

为了避免同学们互相「谋杀」,熊猫老师决定自己对同学们的作文进行抄袭认定工作。

ECNU 的同学们,为了抵抗熊猫老师的剽窃禁止令,不惜一切代价,甚至不惜把作文去掉标点去掉空格全部连在一块儿写。他们觉得,这样就能阻止熊猫老师认出他们的抄袭作文。事实证明,这样的抵抗确实是有效的。熊猫老师现在甚至需要一个程序才能判断一篇作文是否存在抄另外一篇的嫌疑。

当然程序是很傻的,它需要非常傻的逻辑语言才能运行。于是熊猫老师摈弃了他上英语课时一贯的风流潇洒,说出了下面一段话:

有长度均为 的字符串 A 和字符串 B。从 A 字符串中取出若干个互不重叠的长度至少 的子串,将它们按出现顺序组成序列 S(不是串成字符串)。从 B 中也取出若干个,组成序列 T。如果序列 S 恰好与序列 T 相同,那么称这个序列是 A 和 B 的公共单词序列。求 A 和 B 的所有公共单词序列中最长的那一个的长度。

输入格式

不超过 组测试数据。对于每组数据:

第一行是两个整数 ,表示字符串的长度。

第二行和第三行分别有一个长度为 的字符串。

字符串中只会出现小写英文字母。

输出格式

对于每组数据,输出最长公共单词序列的长度。

样例

Input
6 2
acmacm
cmacma
6 3
acmacm
cmacma
5 2
hello
ahelo
Output
2
1
2

提示

第一组样例中,最长公共单词序列可能为 ,也有可能是 ,注意 是不可行的,因为在 B 串中发生了重叠; 也是错误的,因为每个单词长度都应该至少为 2。

a cm ac m
cm ac ma

第二组样例中,最长公共单词序列可能为 ,也有可能是

第三组样例中,最长公共单词序列是

he l lo
a he lo

请注意常数上的优化!

14 人解决,19 人已尝试。

28 份提交通过,共有 104 份提交。

5.4 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年前.

最后提交: 9 月,2 周前.

来源: 2017 CCCC 选拔

题目标签
DP