给定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约束的最长公共子序列。
Input
第1行中给出正整数m,n,p,分别表示给定序列X和Y以及模式子序列P的长度。
接下来的3行分别给出序列X和Y以及模式子串P。
注意:此题输入数据,全是一些小写英文字母。
m<200,n<200,p<200
Output
将计算出的X和Y带有包含子序列P约束的最长公共子串的长度输出
不存在则长度为0。
Sample Input
11 10 4
AATGCCTAGGC
CGATCTGGAC
TGGC
Sample Output
6
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int Maxn = 210; int f[Maxn][Maxn][Maxn]; char s1[Maxn], s2[Maxn], s3[Maxn]; int n, m, p; int _max(int x, int y) { return x > y ? x : y; } int next[Maxn]; int main() { int i, j, k; scanf("%d%d%d", &n, &m, &p); scanf("%s%s%s", s1+1, s2+1, s3+1); j = 0; for(i = 2; i <= p; i++){ while(s3[i] != s3[j+1] && j > 0) j = next[j]; if(s3[i] == s3[j+1]) j++; next[i] = j; } for(i = 0; i <= n; i++){ for(j = 0; j <= m; j++){ for(k = 0; k < p; k++){ f[i+1][j][k] = _max(f[i+1][j][k], f[i][j][k]); f[i][j+1][k] = _max(f[i][j+1][k], f[i][j][k]); if(s1[i+1] == s2[j+1]){ int po = k; while(s1[i+1] != s3[po+1] && po > 0) po = next[po]; if(s1[i+1] == s3[po+1]) po++; f[i+1][j+1][po] = _max(f[i+1][j+1][po], f[i][j][k]+1); } } } } int ans = 0; for(i = 0; i < p; i++) ans = _max(ans, f[n][m][i]); printf("%d\n", ans); return 0; }