最长公共子串

问题

---

给定两个字符串 s1 和 s2 ，求出一个最长的子串，使得该子串既是 s1 的子串，也是 s2 的子串。

样例

---

输入：
s1 = "ABC", s2 = "ABD"
输出：
2 ("AB")

解法

---

设dp[i][j]为以s1[i - 1]和s2[j - 1]为结尾的最长公共子串的长度。
对于$i$和$j$，即字符s1[i - 1]和字符s2[j - 1]，

• 如果s1[i - 1] == s2[j - 1]：
  说明当前字符可以作为以s1[i - 1]和s2[j - 1]为结尾的最长公共子串的一部分。
  则有：$dp[i][j]=dp[i-1][j-1]+1$
  同时记录当前当前公共子串是否是最长公共子串。
• 如果s1[i - 1] != s2[j - 1]：
  因为结尾不同，子串一定不同，所以：$dp[i][j]=0$
  综上有：
  $dp[i][j]=\{\begin{array}{ll}0& \text{if }i=0\text{ or }j=0\text{ or }{S}_1[i-1]\ne S_2[j-1]\\ dp[i-1][j-1]+1& \text{if }{S}_1[i-1]=S_2[j-1]\end{array}$

模版

---

int N, M;
 
int lcs(string s1, string s2)
{
	int res = 0;
	int dp[N][M];
	int n = s1.size();
	int m = s2.size();
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(s1[i - 1] == s2[j - 1])
				{
					dp[i][j] = dp[i - 1][j - 1] + 1;
					res = std::max(ans, dp[i][j]);
				}
 
	return res;
}