// 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;
}
