（2016复旦机试）求最大连续公共字串长度

关键字：动态规划、 最大公共子序列（连续情况）

题目描述：

• 给定两个字符串，求最大公共字串的长度，长度小于1000
• 1111hellow2233
• 2222hellow32

转移方程：

• dp[i][j]：即包含str1[i] 和 str2[j]的两个元素为末尾的时候，的最大连续子序列的长度
• str1[i] == str2[j] 时，dp[i][j] = dp[i-1][j-1]+1;
• str1[i] != str2[j]时，dp[i][j] = 0;

代码：

#include<vector>
using namespace std;
/*
1111hellow2233
2222hellow32
*/
int main() {
	string s1, s2;
	cin >> s1 >> s2;
	int n1 = s1.size();
	int n2 = s2.size();
	vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
	s1 = " " + s1;
	s2 = " " + s2;
	int res = 0;
	//dp[i][j]是最长以i,j为最后字符的最长连续子序列的长度
	for (int i = 1; i <= n1; i++) {
		for (int j = 1; j <= n2; j++) {
			if (s1[i] == s2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = 0;
			}
			res = max(res, dp[i][j]);
		}
	}
	cout << res << endl;
}