两个长字符串的比对，算法设计分析习题

// 1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <string> using namespace std; #define match 5 #define mismatch -1 #define indel -2 int max(int a,int b,int c) { int max=a; if(max<b) max=b; if(max<c) max=c; return max; } int main( ) { cout<<"请输入两个字符串（先输入较长的）："<<endl; string str1,str2; cin>>str1>>str2; int m,n,i,j,k; m=str1.length(); n=str2.length(); //设计一个矩阵来放两个字符对比是的结果 int **D; D= new int*[m]; for(i=0;i<m;i++ ) { D[i] = new int[n]; } for(i=0;i<m;i++) for(j=0;j<n;j++) { if(str1[i]==' '||str2[j]==' ') D[i][j]=-2; else if(str1[i]==str2[j]) D[i][j]=5; else D[i][j]=-1; } //添计分矩阵 int **B; B= new int*[m+1]; for(i=0;i<m+1;i++) { B[i] = new int[n+1]; } for(j=0;j<n+1;j++) B[0][j]=-2*j; for(i=0;i<m+1;i++) B[i][0]=-2*i; for(i=1;i<m+1;i++) { for(j=1;j<n+1;j++) B[i][j]=max(B[i-1][j-1]+D[i-1][j-1],B[i-1][j]+indel,B[i][j-1]+indel); } cout<<"计分矩阵:"<<endl; for(i=0;i<m+1;i++) { for(j=0;j<n+1;j++) cout<<B[i][j]<<'\t'; cout<<endl; } cout<<"计分总和:"<<B[i-1][j-1]<<endl; //回溯法找最优化比对结果 char **arr; arr = new char*[2]; for( i=0;i<2;i++) { arr[i] = new char[n]; } i=m;j=n; int h=0; while ((i!=0)||(j!=0)) { if (B[i][j]==B[i-1][j-1]+D[i-1][j-1]) { arr[0][h]=str1[i-1]; arr[1][h]=str2[j-1]; i=i-1; j=j-1; h=h+1; } else { if (B[i][j]==B[i-1][j]+indel) { arr[0][h]=str1[i-1]; arr[1][h]='-'; i=i-1; h=h+1; } else { if(B[i][j]==B[i][j-1]+indel) { arr[0][h]='-'; arr[1][h]=str2[i-1]; j=j-1; h=h+1; } } } } cout<<"最优化比对结果:"<<endl; for (i=0;i<2;i++) { for(j=h-1;j>=0;j--) cout<<arr[i][j]; cout<<endl; } return 0; }