网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
最长公共子串问题
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 17:55 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 17:55 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 17:55 |
输入文件 | LCS.in | 输出文件 | LCS.out |
【问题描述】最长公共子串问题(LCS.cpp/c/pas)
希腊有一个著名的历史学家,他为了专心写一本史学巨著,而把自己关在一个高塔之上。有一天,他目睹了一场凶杀案的发生,但事后,他惊讶地发现所有围观人的证词都不一样,甚至有的完全相反。于是,他放弃了继续写作的念头。他说:“人们连发生在眼前的事实都分辨不清,我又怎么知道我写的历史是真是假呢?”
虽然历史的真假我们很难辨别,但文章是否抄袭,我们还是可以用所谓的LCS算法解决的。
给出两个字符串S1和S2,我们现在希望了解两个字符串之间的“相似度”。这个相似度是这样定义的:找出第三个字符串S3,组成S3的元素也出现在S1和S2中,而且这些元素必须是以相同的顺序出现,但不必要是连续的。能找到的S3越长则S1和S2就越相似。相似度即是这个S3的长度。例如,当S1="abcde",S2="dabfda",S3就是"abd", S1和S2的相似度就是3。
【输入格式】
第一行为一个整数,表示第一个字符串的长度。
第二行为第一个字符串。
第三行为一个整数,表示第二个字符串的长度。
第二行为第二个字符串。
【输出格式】
一个整数,即两个字符串的相似度。
【输入样例】
5
abccb
5
acabc
【输出样例】
3