BZPRO
#3256. 基因序列相似性问题
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
给定2个长度分别为m和n的DNA序列X和Y，以及一个长度为p的模式子串P．
带有子序列包含约束的最长公共子序列问题就是要找出x和Y的不包含P为其子串的最长公共子序列。
例如，如果给定的DNA序列x和Y分别为X=AATGCCTAGGC，Y=CGATCTGGAC，模式子序列P=TGGC，
则子序列ATCTGGC是X和Y的一个无约束的最长公共子序列
而不包含P为其子串的最长公共子序列是ATCTGC(可能不唯一)。
编程任务：找出给定序列X和Y带有不包含子串P约束的最长公共子序列。
输入格式
第1行中给出正整数m,n,p，分别表示给定序列X和Y以及模式子序列P的长度。
接下来的3行分别给出序列X和Y以及模式子串P。
注意：此题输入数据，全是一些小写英文字母。
m<200,n<200,p<200
输出格式
将计算出的X和Y带有包含子序列P约束的最长公共子串的长度输出
不存在则长度为0。
样例
样例输入
11 10 4
AATGCCTAGGC
CGATCTGGAC
TGGC
样例输出
6
数据范围与提示
BZPRO