lsc.cpp

最长公共子序列(LCS)算法 求两个字符串的最长公共子序列。 X的一个子序列是相应于X下标序列{1, 2, …, m}的一个子序列

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>

#define N 20
char b[N+1][N+1];

void  LCSlength(int m,int n,char x[], char y[])  
{
	char str[20];   //临时buffer
	char d[20];    //存放X序列的递增下表序列
	char e[20];    //存放Y序列的递增下表序列
	int k=0,t=0,i,j;
    int c[N+1][N+1];
	
	for (i=0;i<=m;i++)
		c[i][0]=0;
	for (i=0;i<=n;i++)
		c[0][i]=0;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			if (x[i]==y[j])
			{
				d[k++]=*itoa(i,str,10);
				e[t++]=*itoa(j,str,10);
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]='A';
				
			}
			else if (c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]='B';
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]='C';
			}
		}
		
		
		cout<<endl;
		cout<<"the length of sequence is:"<<c[m][n]<<endl;
		cout<<"corresponding index sequence of X is:"<<endl;
		for(int p=0;p<k;p++)
		{
			cout<<" "<<d[p];
			
		}
		
		cout<<endl;
		
		cout<<"corresponding index sequence of Y is:"<<endl;
		for(int q=0;q<t;q++)
		{
			cout<<" "<<e[q];
		}
		cout<<endl;
		
}
void LCS(int i,int j,char x[])
{
	
				if (i==0 || j==0)
					return;
				if (b[i][j]=='A')
				{
					LCS(i-1,j-1,x);
					cout<<x[i];
				}
				else if (b[i][j]=='B')
					LCS(i-1,j,x);
				else
					LCS(i,j-1,x);
}


void main()
{
	int  lx,ly;
    char X[N+1],Y[N+1];
	cout<<"please input the sequence of X："<<endl;
	cin>>X+1;
	cout<<"please input the sequence of Y："<<endl;
	cin>>Y+1;
	lx=strlen(X+1);
	cout<<"the length of X："<<lx<<endl;
	ly=strlen(Y+1);
	cout<<"the length of Y："<<ly<<endl;
	LCSlength(lx,ly,X,Y);
	cout<<"Longest common subsequence is:"<<endl;
	LCS(lx,ly,X);
	cout<<endl;
}