最长公共子序列

2019-11-08 01:49:43

字体：大中小

来源：转载

供稿：网友

最长公共子序列

和网上的一样，没什么特别的。vs2010编译，就是warning多点。

#include <stdio.h>#include <stdlib.h>#define LEN 20void lcs(char*,int, char*, int, int(*)[]);void PRintMatrix(int(*)[], int, int);void printLCS(int(*)[], int, int,char*);void main(){ //char b[]="BDCABA"; //char a[]="ABCBDAB"; char b[]="cnblogs"; char a[]="belongsaa"; int sizeA=sizeof(a)/sizeof(a[0]); int sizeB=sizeof(b)/sizeof(b[0]); //printf("%s/n",a); int c[LEN][LEN]={0}; lcs(a,sizeA,b,sizeB,c); printMatrix(c,sizeA, sizeB); printLCS(c,sizeA,sizeB,b); system("pause");}void lcs(char* a, int sizeA, char* b, int sizeB, int c[LEN][LEN]){ int i,j; for ( i=0; i<sizeA; i++){ for(j=0; j<sizeB; j++){ if(a[i]!=b[j]){ if(c[i][j+1]>=c[i+1][j]){ c[i+1][j+1]=c[i][j+1]; }else{ c[i+1][j+1]=c[i+1][j]; } } if(a[i]==b[j]){ c[i+1][j+1]=c[i][j] + 1; } } }}void printMatrix(int c[LEN][LEN],int sizeA, int sizeB){ int m,n; for (m=0; m < sizeA; m++){ printf("/n"); for(n=0; n< sizeB; n++){ printf("%d ", c[m][n]); } }}void printLCS(int c[LEN][LEN], int sizeA, int sizeB,char* b){ int m,n,k,kk; char tmp[100]={'/0'}; n=sizeB; m=sizeA; k=0; while(m>0 && n>0){ if(c[m][n]==c[m-1][n]&&c[m-1][n]==c[m][n-1]){ m--; } if(c[m][n]-1==c[m-1][n]&&c[m-1][n]==c[m][n-1]){ m--; n--; //printf("%c ",b[n]); tmp[k]=b[n]; k++; } if(c[m-1][n]>c[m][n-1]){ m--; } if(c[m-1][n]<c[m][n-1]){ n--; } } for(kk=k; kk>=0;kk--){ printf("%c ",tmp[kk]); }}

上一篇：Spring事务原理

下一篇：内部类