YZOJ P2049 [FJOI2013]相似基因序列问题
时间限制:1000MS 内存限制:262144KB
难度:\(6.0\)
-
题目描述
给定 \(2\) 个长度分别为 \(m\) 和 \(n\) 的 DNA 序列 \(X\) 和 \(Y\),以及一个长度为 \(p\) 的模式子序列 \(P\)。带有子序列包含约束的最长公共子序列问题就是要找出 \(X\) 和 \(Y\) 带有包含子序列 \(P\) 约束的最长公共子序列的长度。
例如,如果给定的 DNA 序列 \(X\) 和 \(Y\) 分别为 X=AATGCCTAGGC
,Y=CGATCTGGAC
,模式子序列 P=GTAC
,则子序列 ATCTGGC
是 \(X\) 和 \(Y\) 的一个无约束的最长公共子序列,而包含 \(P\) 为其子序列的最长公共子序列是 GCTAC
。
-
输入格式
第一行中给出正整数 \(m,n,p\),分别表示给定序列 \(X\) 和 \(Y\) 以及模式子序列 \(P\) 的长度。\(m,n,p<300\) 。
接下来的 \(3\) 行分别给出序列 \(X\) 和 \(Y\) 以及模式子序列 \(P\) 。
-
输出格式
将计算出的 \(X\) 和 \(Y\) 带有包含子序列 \(P\) 约束的最长公共子序列的长度输出。如果 \(X\) 和 \(Y\) 不存在包含子序列 \(P\) 的公共子序列,则输出 \(-1\)。
-
样例输入
1 2 3 4 |
11 10 4 AATGCCTAGGC CGATCTGGAC GTAC |
-
样例输出
1 |
5 |