机试算法讲解: 第51题 动态规划之最长公共子序列问题

/*
LCS:最长公共子序列。字符串S中按照先后顺序依次取出若干字符，并将它们排列成一个新的字符串，这个字符串就称为原字符串的子串。有2个字符串S1和S2，求字符串S3同时为S1
    和S2的子串，且要求它的长度最长，确定这个长度。
思路:dp[i][j]表示S1中前i个字符与S2中的前j个字符分别组成的两个前缀字符串的最长公共子串长度，当i.j较小时,dp[0][j]=0。假设已经求得dp[i][j](0<=i<x,0<=j<y)的所有值
     如何有这些值推得dp[x][y]。若S1[x]==S2[y]，即S1中第x个字符和S2中第y个字符相同，且它们各是各自前缀子串的最后字符，那么必存在一个最长公共子串以S1[x]或S2[y]
	 结尾，其他部分等价于S1中前x-1个字符和S2中前y-1个字符的最长公共子串。dp[x][y]=dp[x-1][y-1] +1.若S1[x]!=S2[y],最长公共子串长度为S1中前x-1个字符和S2中前y，
	 个字符的最长公共子串长度  与  S1中前x个字符和S2中前y-1个字符的最长公共子串长度的较大者。即在两种情况下得到最长公共子串不会因为其中一个字符串又增加了一个
	 字符长度而发生改变。dp[x][y]=max{dp[x-1][y],dp[x][y-1]}
关键:
1 递推条件:{dp[i][0] = 0 (0<=i <=n)
           {dp[0][j] = 0 (0<=j <=m)
		   {dp[i][j] = dp[i-1][j-1] + 1,(S1[i]==S2[j])
		   {dp[i][j] = max{dp[i-1][j],dp[i][j-1]},(S1[i]!=S2[j])
2 时间，空间复杂度均为O(L1*L2)
3 易错，这里会遗漏对初始字符的处理，所以比较的是s1[i-1]==s2[j-1] //if(s1[i]==s2[j])
4 dp[i][j]表示两个字符串中前i,j个字符的最长公共子序列
问题:求两个完全小写的字符串的最长公共子串长度。第一行和第二行分别是两个字符串，没有空格间隔，每个字符串的长度不超过100，输出：最长公共子串长度个数
输入:
abcd
cxbydz
输出:
2
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 101

int max(int a,int b)
{
	return a > b ? a:b;
}

int main(int argc,char* argv[])
{
	char s1[N],s2[N];
	int dp[N][N];//用于存放S1中以某个字符结尾，S2中以某个字符结尾的最长公共子串长度
	int i,j;
	while(EOF!=scanf("%s %s",s1,s2))
	{
		int iLen1 = strlen(s1);
		int iLen2 = strlen(s2);
		//设定初始状态
		//for(i = 0 ; i < iLen1 ; i++)
		for(i = 0 ; i <= iLen1 ; i++)
		{
			dp[i][0] = 0;
		}
		//for(j = 0 ; j < iLen2 ; j++)
		for(j = 0 ; j <= iLen2 ; j++)
		{
			dp[0][j] = 0;
		}
		int iMaxLen = -123123123;

		//for(i = 1 ; i < iLen1 ; i++)
		for(i = 1; i <= iLen2;i++)
		{
			//for(j = 1 ; j < iLen2 ; j++)
			for(j = 1 ; j <= iLen2 ; j++)
			{
				//如果两个结尾字符相同，则计算其余长度
				//易错，这里会遗漏对初始字符的处理，所以s1[i-1]==s2[j-1]
				//if(s1[i]==s2[j])
				if(s1[i-1]==s2[j-1])
				{
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				else
				{
					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				}
				//判断最大长度是否需要更新
				if(dp[i][j] > iMaxLen)
				{
					iMaxLen = dp[i][j];
				}
			}//for
		}//for
		printf("%d\n",iMaxLen);
	}//while
	system("pause");
	getchar();
	return 0;
}