(1)最长公共子序列 lcs
*子序列可以是父序列中不连续的部分,但必须是顺序的
S1:ACCGGTCGAGTGCGCGCGGAAGCCGGCCGAA
S2:GTCGTTCGGAATGCCGTTGCTCTGTAA
子序列:GTCGTCGGAAGCCGGCCGAA
求法:
C[i,j]=0 i=0 || j=0
C[i,j]=C[i-1,j-1]+1 x[i]=y[j]
C[i,j]=max(c[i,j-1],c[i-1,j]) x[i]!=x[j]
#include<iostream>
#include<string>
using namespace std;
void print(char b[100][100],char x[],int m,int n){
if(m==0 || n==0) return ;
if(b[m][n]=='3'){
print(b,x,m-1,n-1);
cout<<x[m];
}
else if(b[m][n]=='2') print(b,x,m-1,n);
else print(b,x,m,n-1);
}
void lcs(char x[],char y[]){
int m=strlen(x)-1;
int n=strlen(y)-1;
int c[m+1][n+1];
char b[m+1][100];
for(int i=1;i<=m;i++) c[i][0]=0;
for(int j=1;j<=n;j++)c[0][j]=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]='3';
}
else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]='2';
}
else{
c[i][j]=c[i][j-1];
b[i][j]='1';
}