对于连续的最大串,我们称之为子串....非连续的称之为公共序列..
代码:
非连续连续
1 int LCS(char a[],char b[],char sav[]){
2 int lena=strlen(a);
3 int lenb=strlen(b);
4 int i,j;
5 vector<vector<int> >mat(lena+1);
6 for(int i=0;i<=lena;i++)
7 mat[i].resize(lenb+1,0);
8 for(i=1;i<=lena;i++){
9 for(j=1;j<=lenb;j++){
10 if(a[i-1]==b[j-1])
11 mat[i][j]=mat[i-1][j-1]+1;
12 else
13 mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
14 }
15 }
16 i=lena-1;
17 j=lenb-1;
18 int k=0;
19 while(i!=-1&&j!=-1) {
20 if(a[i]==b[j]){
21 sav[k++]=a[i];
22 i--;
23 j--;
24 }
25 else{
26 if(mat[i+1][j+1]==mat[i][j]){
27 i--;
28 j--;
29 }
30 else{
31 if(mat[i][j+1]>=mat[i+1][j]) i--;
32 else j--;
33 }
34 }
35 }
36 return k;
37 }
连续子串
代码:
1 int LCS(char a[],char b[],char sav[]){
2 int lena=strlen(a);
3 int lenb=strlen(b);
4 int i,j,k=0,x=0;
5 vector<vector<int> >lcs(lena+1);
6 for(int i=0;i<=lena;i++)
7 lcs[i].resize(lenb+1,0);
8 for(i=1;i<=lena;i++){
9 for(j=1;j<=lenb;j++)
10 if(a[i-1]==b[j-1]){
11 lcs[i][j]=lcs[i-1][j-1]+1;
12 if(k<lcs[i][j]){
13 x=i;
14 k=lcs[i][j];
15 }
16 }
17 }
18 strncpy(sav,a+(x-k),k);
19 return k;
20 }