最长公共子序列

Contents

1. 1. 题目描述
2. 2. 最长公共子序列
   1. 2.1. 最优解(最大长度)
   2. 2.2. 最优解的序列
3. 3. 完整代码

求解两个字符串的最长公共子序列

题目描述

最长公共子序列

最优解(最大长度)

void LCSlength(int m,int n,char *x,char *y,int **c,int **b)
{
	int i,j;
	for(i=1;i<=m;i++)c[i][0]=0;   
	for(i=1;i<=n;i++)c[0][i]=0;  //i=0或者j=0,最长公共子序列为空 
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			if(x[i]==y[j])      //x[i]=y[j]时,c[i][j]=斜上方的c[i-1][j-1]+1 
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;      //b[i][j]=1;表示c[i][j]来自斜上方的值+1而来 
			}
			        //下面 max(c[i-1][j],c[][j-1]) 
			else if(c[i-1][j]>c[i][j-1]) 
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;     //b[i][j]=2;表示c[i][j]来自正上方的值+1而来
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=3;     //b[i][j]=3;表示c[i][j]来自左方的值+1而来
			}
		}
}

最优解的序列

void LCS(int i,int j,char *x,char **b)
{
	if(i==0||j==0)return;
	if(b[i][j]==1)
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i];
	}
	else if(b[i][j]==2)
		LCS(i-1,j,x,b);
	else 
		LCS(i,j-1,x,b);
}

完整代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
int c[2000][2000];
char x[2000],y[2000];
/*最优解，输出公共序列
void LCS(int i,int j)
{
	if(i==0||j==0)return;
	if(b[i][j]==1)
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i-1];
	}
	else if(b[i][j]==2)
		LCS(i-1,j);
	else 
		LCS(i,j-1);
}*/
int LCSLength(int m,int n)
{
	int i, j;
	int len;
	for (i = 1; i <= m; i++)
		c[i][0] = 0;
	for (i = 1; i<=n; i++)
		c[0][i] = 0;
	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (x[i-1]==y[j-1])
			{
				c[i][j] = c[i - 1][j - 1] + 1;
			}
			else if (c[i - 1][j] >=c[i][j - 1])
			{
				c[i][j] = c[i - 1][j];
			}
			else
			{
				c[i][j] = c[i][j - 1];
			}
		}
	}
	len = c[m][n];
	return len;
}
int main(void)
{
	int m,n, len;
	while(cin >> x){
	cin >> y;
	m= strlen(x);
	n= strlen(y);
	len = LCSLength(m,n);
	cout << len << endl;
	}
}