👉引言💎
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💎求解最长公共子串
既然我们已经知道最长公共子序列的解法，那么相应地子串解法是不是也迎刃而解了呢？ 首先，子串与子序列什么区别呢？ 这里我要声明一下，有些题解将子串与子序列混为一谈，标题为子串，但其实求解的是子序列，这其实是不对的，子串是连续的，而子序列既可以连续也可以不连续，只要字符串里顺序包含序列里的字符即可。 还记得求解子序列时我们是怎样列出条件，从记忆化搜索到动态规划的吗？
没错，就是看有哪些情况与假设，对于子序列来说，就是
1.str1[i]与str2[j]相同时，此时寻找process(i-1,j-1),然后+1
2.str1[i]与str2[j]不同时，此时有两种情况： process(i,j-1) or process(i-1,j)
然后取max，如果要记录路径的话，也就是存在多个解取最优时，就需要再记录一下 方向，以便于推导路线
那么，对于 子串呢？因为必须连续，所以 当str1[i]与str2[j]相同时，去寻找上面三种情况；当不相同时，则该i处字符就不算了（必须连续），直接递归寻找 以i-1或j-1位置的字符结尾的字符串 的子串
👉记忆化搜索
int process(string& str1, string& str2, int i, int j) {//以i，j为结尾下标 if (dp[i][j])//如果该位置的答案已经被求解出来，那么直接返回答案 { return dp[i][j]; } if (i == 0 || j == 0) {//分析各种边界条件（当两字符串其中一个或者都只剩下一个字符时，分析两者相等与不等的情况），找递归出口 if (str1[i] == str2[j]) { dp[i][j] = 1; } return dp[i][j]; } int p3 = 0, p1 = 0, p2 = 0; if (str1[i] == str2[j]) { p1 = process(str1, str2, i, j - 1);//找该位置的最大值 p2 = process(str1, str2, i - 1, j); p3 = process(str1, str2, i - 1, j - 1) + 1; } else { process(str1, str2, i, j - 1); process(str1, str2, i - 1, j); } dp[i][j] = max(p1, max(p2, p3));//其实如果不求具体值，递归里面就可以去找最大值，但是因为要找i，j下标，所以最后去遍历dp表 return dp[i][j]; } int longestCommonSubsequence(string text1, string text2) { dp.resize(text1.size(), vector<int>(text2.size())); flag.resize(text1.size(), vector<int>(text2.size())); int ana = process(text1, text2, text1.size() - 1, text2.size() - 1); return ana; } int main() { longestCommonSubsequence("WOAINIyishengyishi", "WOAINI") ; for (vector<int>t : dp) { for (int i : t)cout << i << " "; cout << endl; } return 0; }
子串的路径输出更加简单，我们不需要再去建立数组，而只需要找到dp表里最大值的下标，然后通过长度倒推即可请往下看
👉动态规划
int main() { string s1 = "yongwangzhiqian", s2 = "yong"; int len1 = s1.size(), len2 = s2.size(); vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1)); int max = 0, path1 = 0, path2 = 0; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (s1[i - 1] == s2[j - 1]) {//int t=max(dp[i][j-1],dp[i-1][j]);如果直接改是这样的，但是优化一下就是如下了 dp[i][j] = dp[i - 1][j - 1] + 1;// dp[i][j] = max(dp[i - 1][j - 1] + 1,t); if (dp[i][j] > max) { max = dp[i][j]; path1 = i - 1; path2 = j - 1;//得到下标 } } } } cout << max << " " << path1 << " " << path2 << endl; string ans((s1.begin() + path1 + 1 - max), (s1.begin() + path1 + 1)); cout << ans << endl;//左闭右开，末尾取不到，所以加1 return 0; }
🌹写在最后💖： 路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹
