这个问题经常运用在判断两种生物的相似度—-DNA比对上。对比俩串的方式有很多种，例如如果一个串是另一个的字串，那么可以说两个串是相似的：如果将一个串转换为另一个串的操作很少，那么也可以说这两个串是相似的。另一种衡量俩串S1,S2S1,S2的相似度方式为：寻找第3个串S3S3，它的所有元素也都出现在S1S1和S2S2中，且在三个串中出现的顺序都相同，但在S1,S2S1,S2中不要求连续出现。我们将最后一种相似的概念描命名最长公共子序列问题。
其形式化定义如下：给定一个序列X=⟨x1,x2…,xm⟩X=⟨x1,x2…,xm⟩，另一个序列Y=⟨y1,y2,…,yk⟩Y=⟨y1,y2,…,yk⟩满足如下条件时成为XX的子序列(sunsequence)，即存在一严格递增的XX的下标序列⟨i1,i2,…,ik⟩⟨i1,i2,…,ik⟩，对所有j=1,2,…,kj=1,2,…,k满足ij=zjij=zj。例如，Z=⟨B,C,D,B⟩Z=⟨B,C,D,B⟩是X=⟨A,B,C,B,D,A,B⟩X=⟨A,B,C,B,D,A,B⟩的子序列，对应的下标为⟨2,3,5,7⟩⟨2,3,5,7⟩。
给定一个序列X=⟨x1,x2…,xm⟩X=⟨x1,x2…,xm⟩，对i=1,2,…,ki=1,2,…,k，定义XX的第ii前缀为Xi=⟨x1,x2…,xi⟩Xi=⟨x1,x2…,xi⟩。
刻画最长公共子序列的特征
LCSLCS的最优子结构：令X=⟨x1,x2…,xm⟩X=⟨x1,x2…,xm⟩和Y=⟨y1,y2,…,yn⟩Y=⟨y1,y2,…,yn⟩为两个序列，Z=⟨z1,z2,…,zk⟩Z=⟨z1,z2,…,zk⟩为XX和YY的任意LCSLCS。
1.如果xm=ynxm=yn，则zk=xm=ynzk=xm=yn且Zk−1Zk−1是Xm−1Xm−1和Yn−1Yn−1的一个LCSLCS。
2.如果xm≠ynxm≠yn，则zk≠xmzk≠xm且ZZ是Xm−1Xm−1和YY的一个LCSLCS。
3.如果xm≠ynxm≠yn，则zk≠ynzk≠yn且ZZ是XX和Yn−1Yn−1的一个LCSLCS。
一个递归解
我们定义c[i,j]c[i,j]表示XiXi和YjYj的LCSLCS的长度。则根据LCSLCS问题的最优子结构性质，可得如下公式：
c[i,j]=⎧⎩⎨⎪⎪0c[i−1,j−1]+1max(c[i,j−1],c[i−1,j])ifi=0orj=0ifi,j>0andxi=yjifi,j>0andxi≠yj
c[i,j]={0ifi=0orj=0c[i−1,j−1]+1ifi,j>0andxi=yjmax(c[i,j−1],c[i−1,j])ifi,j>0andxi≠yj
源代码
#include #include #include #include using namespace std;
//ACCGTCGAGTGCGCGGAAGCCGGCCGAA & CTCGTTCGGAATGCCGTTGCTCTGTAAA
string temp_strX = { "#ACCGTCGAGTGCGCGGAAGCCGGCCGAA" }, temp_strY = { "#CTCGTTCGGAATGCCGTTGCTCTGTAAA" };
//Memoized of Lcs
pair>,vector>> Lcs_Length(const string &temp_strX, const string &strY) {
auto temp_m = temp_strX.size() - 1, temp_n = temp_strY.size() - 1;
vector> temp_VecB, temp_VecC;
temp_VecB.resize(temp_m + 1);
temp_VecC.resize(temp_m + 1);
for(auto &i : temp_VecB) {
i.resize(temp_n + 1);
}
for(auto &i : temp_VecC) {
i.resize(temp_n + 1);
}
for(auto i = 1; i <= temp_m; ++i) {
temp_VecC[i][0] = 0;
}
for(auto j = 0; j <= temp_n; ++j) {
temp_VecC[0][j] = 0;
}
for(auto i = 1; i <= temp_m; ++i) {
for(auto j = 1; j <= temp_n; ++j) {
if(temp_strX[i] == temp_strY[j]) {
temp_VecC[i][j] = temp_VecC[i - 1][j - 1] + 1;
temp_VecB[i][j] = -1;
}
else if(temp_VecC[i - 1][j] >= temp_VecC[i][j - 1]) {
temp_VecC[i][j] = temp_VecC[i - 1][j];
temp_VecB[i][j] = -2;
}
else {
temp_VecC[i][j] = temp_VecC[i][j - 1];
temp_VecB[i][j] = -3;
}
}
}
return make_pair(temp_VecC, temp_VecB);
}
void Print_Lcs(const vector> & temp_VecB, const string &temp_strX, const size_t &i, const size_t &j) {
if(i == 0 || j == 0) {
return;
}
if(temp_VecB[i][j] == -1) {
Print_Lcs(temp_VecB, temp_strX, i - 1, j - 1);
cout << temp_strX[i];
}
else if(temp_VecB[i][j] == -2) {
Print_Lcs(temp_VecB, temp_strX, i - 1, j);
}
else {
Print_Lcs(temp_VecB, temp_strX, i, j - 1);
}
}
int main() {
auto temp_pair = Lcs_Length(temp_strX, temp_strY);
Print_Lcs(temp_pair.second, temp_strX, temp_strX.size() - 1, temp_strY.size() - 1);
return 0;
}
0.0分
0 人评分
