312003 - 最长公共子序列问题

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

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

第二行为第一个字符串。

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

第四行为第二个字符串。

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