LCS 最长公共字串算法实现

#include <iostream> using namespace std; #define N 100 int c[N][N]={0}; void print(char* x,int i,int j) { if (i < 0 || j < 0) { return; } if (c[i][j] == c[i][j-1]) { print(x,i,j-1); } else if (c[i][j] == c[i-1][j]) { print(x,i-1,j); } else if (c[i][j] == c[i-1][j-1] + 1) { print(x,i-1,j-1); cout<<i<<":"<<x[i]<<"/t"; } } int lcs(char* x, char* y,int m, int n) { if (m < 0 || n < 0) { return 0; } if (x[m] == y[n]) { return lcs(x,y,m-1,n-1)+1; } else { int t2 = lcs(x,y,m,n-1); int t1 = lcs(x,y,m-1,n); return t1 > t2 ? t1 : t2; } } int main(int argc,char** args) { char *x = "abcdhchk"; char *y = "ffbdgghph"; cout<<lcs(x,y,strlen(x)-1,strlen(y)-1)<<endl; for (int j = 0; j < strlen(y); j++) { cout<<"/t"<<y[j]; } cout<<endl; for (int i = 0; i < strlen(x); i++) { for (int j = 0; j < strlen(y); j++) { c[i][j] = lcs(x,y,i,j); } } for (int i = 0; i < strlen(x); i++) { cout<<x[i]<<"/t"; for (int j = 0; j < strlen(y); j++) { cout<<c[i][j]<<"/t"; } cout<<endl; } print(x,strlen(x)-1,strlen(y)-1); }