最大公共子串-动态规划

标题：最大公共子串

最大公共子串长度问题就是： 求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“abcdkkk” 和 “baabcdadabc”， 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

首先请你们自己画出一个父串和子串的矩阵，例如：dp[i][j]

图片说明：红色框里面的为dp数组内容。绿色和淡黄色分别表示abcd和abc的匹配结果。

Ps：初始值都为0,dp[i][j]。
old_max = 0;
递推式：

• dp[i][j] = dp[i-1][j-1]+1;
• max(dp[i][j],old_max);、

dp含义：i,j分别表示上面矩阵的下标，如果father[i-1]==son[j-1]，则当前dp[i][j] = 以前匹配数+1。由于可能出现多个相同字符串，所以要选取最大的字符串长度old_max=max(dp[i][j],old_max);

为什么要用old_max？
因为，s1：abcdhuvwxyzcd和s2：efabcnabcdefuvwxyz。
在匹配时，我们会先匹配到abc，所以长度为4。后面又匹配到了uvwxyz长度为6,很明显我们要更新最大长度。

算法主要思想：

1. 选取父串一个字符（下标），查看子串的匹配情况，填到dp数组中。
2. 父串后移，字串从头开始。
3. 父串全部扫描完成。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 256
int f(const char* s1, const char* s2)
{
	int dp[N][N];
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	int i,j;
	
	memset(dp,0,sizeof(int)*N*N);
	int old_max = 0;
	for(i=1; i<=len1; i++){
		for(j=1; j<=len2; j++){
			if(s1[i-1]==s2[j-1]) {
				dp[i][j] = dp[i-1][j-1]+1;
				old_max = max(dp[i][j],old_max);
			}
		}
	}	
	return old_max;
}

int main()
{
	printf("%d\n", f("abcdgkkk", "baabcdgadabc"));
	return 0;
}