做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


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

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

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

【问题描述】最长公共子串问题(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

输入

输出

提示

标签

[上一题][提交][讨论版][状态][下一题]