基因序列相似性问题

时间限制:10s    【提交】    空间限制:256MB

题目描述

给定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的长度。m<200,n<200,p<200。接下来的3行分别给出序列X和Y以及模式子串P。

注意:此题输入数据,全是一些小写英文字母。


输出格式

将计算出的X和Y带有包含子序列P约束的最长公共子串的长度输出,不存在则长度为0。


样例输入

input 1
11 10 4
AATGCCTAGGC
CGATCTGGAC
TGGC


input 2
100 100 50
bbbbaabbaabaaababaaabbbbaaaaaabbbbabbbbaaaaaabaabaaaabbbabaaabbbaaaababbaaababababbaaaababbbaaaaaaab
baabaabbabbaaabaabbababbabaababbbababbbaaabbbbabaaabaabbabababaaaaaaaabbaaaaabbbbbbababbbbabbbaaaaba
bbabbbaababaaaabaaaaabbaaababbbbbabbabbabababaaaab

样例输出

output 1
6

output 2
78


提示

对于100%的数据:0<n,m,p<=200;


题目来源

Dp Kmp