sy5.cpp

两个任意字符串的最长公共子序列的C++实现

#include<iostream>
using namespace std;
void lsc(char a[],int la,char b[],int lb);
void main()
{
	char a[20];
	char b[20];
	int i=0;
	int num=0;
	char c;
	a[0]=' ';
	i=1;
	cout<<"请输入字符串a:"<<endl;
	do
	{
		c=cin.get();
		if(c=='\n')
			break;
		if(c!=' ')
a[i++]=c;
	}while(i<20);
	int len1=i;
	i=1;
	cout<<"请输入字符串b:"<<endl;
	do
	{
		c=cin.get();
		if(c=='\n')
			break;
		if(c!=' ')
			b[i++]=c;
	}while(i<20);
	int len2=i;
	lsc(a,len1,b,len2);
}
void lsc(char a[],int la,char b[],int lb)
{
	char s[15];
	char output[15];
	int m[15][15];
	for(int i=0;i<la;i++)
	{
		m[i][0]=0;
	}
	for(i=0;i<lb;i++)
	{
		m[0][i]=0;
	}
	int flag=0;
	int index=0;
	for(i=1;i<la+1;i++)
	{
		for(int j=1;j<lb+1;j++)
			if(a[i]==b[j])
			{
				m[i][j]=m[i-1][j-1]+1;
			}
			else 
			{
				if(m[i-1][j]<m[i][j-1])
					m[i][j]=m[i][j-1];
				else 
					m[i][j]=m[i-1][j];
			}
	}

int max=m[la-1][lb-1];
cout<<"the max length is:"<<max<<endl;
i=la-1;
int j=lb-1;
int no=0;
while(i>=0&&j>=0)
{
	if(m[i][j]==max)
	{
		if(a[i]==b[j])
		{
			output[no]=a[i];
			no++;
			i--;
			j--;
			max--;
		}
		else
		{
			if(m[i-1][j]<m[i][j-1])
				j--;
			else
				i--;
		}
	}
}
for(i=no-1;i>=0;i--)
cout<<output[i]<<' ';
cout<<endl;

}