【动态规划】最长公共子序列&最长公共子串

最长公共子序列

参考：最长子序列

最长公共子串

参考添加链接描述

void findMaxCommonStr(string s1, string s2)
{
	if (s1.length()>s2.length())
		swap(s1, s2);//s1用于保存较短的子串
	int len1 = s1.length(), len2 = s2.length();
	int maxLen = 0, start = 0;
	vector<vector<int> >dp(len1 + 1, vector<int>(len2 + 1, 0));
	for (int i = 1; i <= len1; ++i)
	for (int j = 1; j <= len2; ++j)
	{
		if (s1[i - 1] == s2[j - 1])
		{
			dp[i][j] = dp[i - 1][j - 1] + 1;
			if (dp[i][j]>maxLen)   //此 if() 写在if (s1[i - 1] == s2[j - 1]) 里面，能保证是第一次出现的，并且保证取到最大长度
			{
				maxLen = dp[i][j];
				start = i - maxLen;//记录最长公共子串的起始位置，并且记录的只有第一次出现 maxLen 的位置。因为如果以后出现相等的最大的，不会进行交换
			}
		}
	}
	cout << s1.substr(start, maxLen) << endl;
}
int main()
{
	string s1, s2;
	while (cin >> s1 >> s2)
	{
		findMaxCommonStr(s1, s2);
	}
	return 0;
}