今天学习了LCS,用动态规划解决最长公共子序列和最长公共子串。 

LCS

LCS有俩种一个是最长公共子序列(Longest Common Sequence)另外一个是最长公共子串(Longest Common Substring)。

最长公共子序列

LCS最长公共子序列是指在俩个字符串当中公共的“序列”。我们通常要求的是长度。

比如

A串1238945999

B串123774519

则最长公共子序列为

A串1238945999

B串123774519

为123459长度为6序列是不一定连续连续的叫做最长公共子串。

如何实现?

DP动态规划

首先我们看上面这个

i代表A串的位置j代表B串的位置。

如果当前a[i]==b[j],说明当前位置有一个相同那么就是前面不取ij所得到的答案+1,也就是dp[i-1][j-1]+1

如果不相等那么我们就要考虑俩种情况了是不考虑当前a串i的位置dp[i][j-1]大还是当前不考虑b串j的位置(dp[i-1][j])大。

所以就变成了

代码如下

#include<stdio.h>
#define N 1000
char s1[N+3],s2[N+3];
char dp[N+5][N+5];
int max(int a,int b)
{
	if(a>b) return a;
	return b;
}
int main()
{
	int i,j;
	scanf("%s%s",s1+1,s2+1);
	for(i=1;s1[i];i++)
	{
		for(j=1;s2[j];j++)
		{
			if(s1[i]==s2[j])
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			}
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	printf("%d",dp[i-1][j-1]);
}

最长公共子串

最长公共子串是找公共的子串也是运用到了DP。

这个和上面不同的就是字符要是连续的。

比如

A串1238945999

B串123454519

答案为3 是123

我们还是需要分情况讨论

如果当前B串i的位置和A串j的位置相等那么我们可以知道如果它为dp[i-1][j-1]+1

因为dp[i-1][j-1]要么不等于为0要么等于为另外一个数字。

如果不相等直接为0即可。

在这个过程中找最大值即可。

代码为

#include<stdio.h>
#define N 1000
char s1[N+3],s2[N+3];
char dp[N+5][N+5];
int m;
int max(int a,int b)
{
	if(a>b) return a;
	return b;
}
int main()
{
	int i,j;
	scanf("%s%s",s1+1,s2+1);
	for(i=1;s1[i];i++)
	{
		for(j=1;s2[j];j++)
		{
			if(s1[i]==s2[j])
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			}
			else dp[i][j]=0;
			if(m<dp[i][j]) m=dp[i][j];
		}
	}
	printf("%d",m);
	return 0;	
}