最长公共子串
进阶最长公共子串要求子串连续，与 LCS 不同。
// 算法讲解
最长公共子串
找两个字符串中最长的公共连续子串。
待机
速度 中
待机 ⌨1int longestCommonSubstring(string s1, string s2) {
2 int m = s1.size(), n = s2.size();
3 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
4 int maxLen = 0;
5 for (int i = 1; i <= m; i++)
6 for (int j = 1; j <= n; j++) {
7 if (s1[i-1] == s2[j-1]) {
8 dp[i][j] = dp[i-1][j-1] + 1;
9 maxLen = max(maxLen, dp[i][j]);
10 }
11 }
12 return maxLen;
13}
复杂度分析
时间 O(mn)
空间 O(mn)
最优 O(mn)
最坏 O(mn)
算法讲解
最长公共子串要求子串在两个字符串中都是连续出现的。
dp[i][j] 表示以 s1[i] 和 s2[j] 结尾的最长公共子串长度。
若 s1[i] == s2[j]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。
时间复杂度 O(mn)，空间复杂度可优化到 O(n)。