#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
static int e; //标志位 防止重复走走过的路径
int LCS(char *,char *);
void ShowCS(int *,int,int,int,char *);
void findplace(int *,int *,int,int,int,int,int,int,char *);
void main()
{
char *A,*B,*p;
char ch;
int n,i,count;
cout << endl;
cout << " ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" <<endl;
cout << " ◎---ＷＥＬＣＯＭＥ ＴＯ ＤＩＳＰＬＡＹ---◎" << endl;
cout << " ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" <<endl;
cout << endl;
do
{
A=(char *)malloc(81);
B=(char *)malloc(81);
cout<<" 请选择手动输入（H）还是随机产生字符串（R）？";
cin>>ch;
while(ch!='H' && ch!='h' && ch!='R' && ch!='r')
{
cout<<" 请选择手动输入（H）还是随机产生字符串（R）？";
cin>>ch;
}
if(ch=='H' || ch=='h')
{
cout<<" 请输入字符串A：";
cin.get(); //吸收前面的回车键
cin.getline(A,81);
cout<<" 请输入字符串B：";
cin.getline(B,81);
}
else if(ch=='R' || ch=='r')
{
cout<<" 请输入要产生的字符串A的字符数：（<=80）";
cin>>n;
for(i=0,p=A;i<n;i++,p++)
{
*p=char(rand()%26+65);
}
*p=0;
cout<<" 请输入要产生的字符串B的字符数：（<=80）";
cin>>n;
for(i=0,p=B;i<n;i++,p++)
{
*p=char(rand()%26+65);
}
*p=0;
cout << " " ;
for(p=A;*p!=0;p++)
{
cout<<*p;
}
cout<<endl;
cout << " " ;
for(p=B;*p!=0;p++)
{
cout<<*p;
}
cout<<endl;
}
cout<<" 它们的最长子序列有："<<endl;
count=LCS(A,B);
free(A);
free(B);
cout<<" 这两个字符串的最长子序列长为："<<count<<endl;
cout << " ----------------------------------------------" << endl;
cout<<" 是否继续比较其他字符串？（Y/N）";
cin>>ch;
}while(ch=='Y' || ch=='y');
cout << " ---To Be End---" <<endl;
}
int LCS(char *A,char *B)
{
int n=0,m=0,i,j,lcs;
char *p;
int *L;
p=A;
while(*p!=0)
{
n++;
p++;
}
p=B;
while(*p!=0)
{
m++;
p++;
}
L=(int *)malloc((n+1)*(m+1)*sizeof(int)); //用一维数组模拟二维数组
for(i=0;i<=n;i++)
{
*(L+i*(m+1))=0;
}
for(j=0;j<=m;j++)
{
*(L+j)=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(*(A+i-1)==*(B+j-1))
*(L+i*(m+1)+j)=*(L+i*(m+1)+j-m-2)+1;
else if(*(L+i*(m+1)+j-1)>*(L+i*(m+1)+j-m-1))
*(L+i*(m+1)+j)=*(L+i*(m+1)+j-1);
else
*(L+i*(m+1)+j)=*(L+i*(m+1)+j-m-1);
}
}
lcs=*(L+n*m+n+m);
ShowCS(L,n,m,lcs,A);
free(L);
return lcs;
}
void ShowCS(int *L,int n,int m,int count,char *A)
{
int *LCS;
LCS=(int *)malloc(count*sizeof(int));
e=0;
findplace(L,LCS,0,0,n,m,0,count,A);
free(LCS);
}
void findplace(int *L,int *LCS,int i,int j,int n,int m,int num,int count,char *A)
{
int t=0;
if(m-j>=count-num && n-i>=count-num && *(L+i*(m+1)+j)==*(L+i*(m+1)+j+1) && *(L+i*(m+1)+j)==*(L+(i+1)*(m+1)+j))
{
if(*(L+i*(m+1)+j)+1==*(L+(i+1)*(m+1)+j+1))
{
*(LCS+num)=i+1;
t=1;
num++;
if(num==count)
{
cout << " " ;
for(int p=0;p<count;p++)
{
cout<<*(A+*(LCS+p)-1);
}
cout<<endl;
t=0;
num--;
}
if(t==1)
{
e=0;
i++;
j++;
findplace(L,LCS,i,j,n,m,num,count,A);
}
}
else
{
if(e==0)
findplace(L,LCS,i,j+1,n,m,num,count,A);
e=1;
findplace(L,LCS,i+1,j,n,m,num,count,A);
}
}
}
评论0