2164: 宝典2第十一章最长公共子串问题

【问题描述】最长公共子串问题(LCS.cpp/c/pas)

希腊有一个著名的历史学家，他为了专心写一本史学巨著，而把自己关在一个高塔之上。有一天，他目睹了一场凶杀案的发生，但事后，他惊讶地发现所有围观人的证词都不一样，甚至有的完全相反。于是，他放弃了继续写作的念头。他说：“人们连发生在眼前的事实都分辨不清，我又怎么知道我写的历史是真是假呢？”

虽然历史的真假我们很难辨别，但文章是否抄袭，我们还是可以用所谓的LCS算法解决的。

给出两个字符串S₁和S₂，我们现在希望了解两个字符串之间的“相似度”。这个相似度是这样定义的：找出第三个字符串S₃，组成S₃的元素也出现在S₁和S₂中，而且这些元素必须是以相同的顺序出现，但不必要是连续的。能找到的S₃越长则S₁和S₂就越相似。相似度即是这个S₃的长度。例如，当S₁="abcde"，S₂="dabfda"，S₃就是"abd"， S₁和S₂的相似度就是3。

【输入格式】

第一行为一个整数，表示第一个字符串的长度。

第二行为第一个字符串。

第三行为一个整数，表示第二个字符串的长度。

第二行为第二个字符串。

【输出格式】

一个整数，即两个字符串的相似度。

    【输入样例】

    5

    abccb

    5

    acabc

    【输出样例】

    3