题目描述：
好久没做题目了，近期刷抖音碰到一个题目，乍一看不是很难，但是手生了，就写个玩玩，大家轻喷。
两个字符串比较，如abcdefg和25abdfxx，返回：位置0多出:25；位置2缺少:c；位置4缺少:e；位置6错误，应为g。
解题思路：
我看很多人说双指针法、动态规划能解，我暂时没想那么多，就用了简单的双循环+滑动窗口。
- 取idx1和idx2作为滑动窗口起点。以字符串1为基准，遍历字符串2寻找相同的字符。
- 当两个字符一致时，判断下j和idx2的大小情况，如果j大且i和idx1一致，说明字符串2相同字符前面有一段字符是多出的。之后，将idx1加1，再使idx2等于j+1，这样可以使两个字符串的滑动窗口从相同字符后的一个位置开始。
- 如果i大于idx1，且j和idx2一致，同理，说明字符串1相同字符前面缺少了一段字符。之后，idx2加1，idx1等于i+1即可。
- 如果i大于idx1，j也大于idx2，说明两个字符串相同字符前，各有一段不相同字符，即匹配错误。
- 若上述三个条件都不满足，那就说明碰到了连续相同字符串。令idx1和idx2都加1，跳过即可。
- 如果i走到最后都没找到匹配对象，则从idx1到字符串1结尾所有字符都匹配失败了。
测试代码：
#include <iostream> #include <string> using namespace std; void compareStrings(std::string str1, std::string str2) { int len1 = str1.length(); int len2 = str2.length(); int idx1 = 0; int idx2 = 0; for (int i = 0; i < len1; ++i) { for (int j = idx2; j < len2; ++j) { if (str1[i] == str2[j]) { if (j > idx2 && i == idx1) { cout << "位置" << i << "多出：" << str2.substr(idx2, j - idx2) << endl; idx1++; idx2 = j + 1; } else if (i > idx1 && j == idx2) { cout << "位置" << idx1 << "缺少：" << str1.substr(idx1, i - idx1) << endl; idx1 = i + 1; idx2++; } else if (i > idx1 && j > idx2) { cout << "位置" << idx1 << "错误，应为：" << str1.substr(idx1, i - idx1) << endl; idx1 = i + 1; idx2= j + 1; } else{ idx1++; idx2++; } break; } } if (i == (len1 - 1) && (idx1 < len1)) { cout << "位置" << idx1 << "错误，应为：" << str1.substr(idx1, i - idx1 + 1) << endl; } } } int main() { std::string str1 = "abcdefg"; std::string str2 = "25abdfxx"; cout << "字符串1：" << str1 << endl; cout << "字符串2：" << str2 << endl; compareStrings(str1, str2); return 0; }
测试结果：
字符串如题目要求时，结果如下，可以发现是满足的。
加几个字符再试试，依然可行。
中间内容再打乱一些，暂无问题。
多几个重复字符，按照我的逻辑，输出结果是对的，但不知道题目是不是这意思。
如果代码有什么需要改进的或者有什么bug，欢迎评论留言，我会及时更正以免误导他人~
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
有朋友提出了问题，所以我对算法进行了改进。
- 基于动态规划表获取两个字符串的最长非连续重复子串。
- 用子串作为参照物，逐一字符遍历。取两个字符串在该字符前的字符串比较，根据不同情况做出不同反馈，具体参见代码和注释。
测试代码：
#include <iostream> #include <string> #include <vector> #include <math.h> #include <algorithm> using namespace std; // 获取最长重复子串（可不连续） string getSubString(std::string str1, std::string str2) { int len1 = int(str1.length()); int len2 = int(str2.length()); // 动态规划 vector<vector<int>> m(len1 + 1, vector<int>(len2 + 1, 0)); vector<vector<string>> s(len1 + 1, vector<string>(len2 + 1, "")); for (int i = 1; i <= len1; ++i){ for (int j = 1; j <= len2; ++j){ if (str1[i - 1] == str2[j - 1]){ m[i][j] = m[i - 1][j - 1] + 1; s[i][j] = s[i - 1][j - 1] + str1[i - 1]; } else{ if (m[i - 1][j] > m[i][j - 1]){ m[i][j] = m[i - 1][j]; s[i][j] = s[i - 1][j]; } else{ m[i][j] = m[i][j - 1]; s[i][j] = s[i][j - 1]; } } } } return s[len1][len2]; } // 比较字符串 void compareString(string str1, string str2, string substr) { int len1 = int(str1.length()); int len2 = int(str2.length()); int len3 = int(substr.length()); // 以重复子串字符遍历 // 若截止到第一个重复字符，t1空，t2有，那就是多出；t1有，t2空，那就是缺少。 // 两个都空说明连续重复字符；若两个都不空，则说明错误。 // 缺少和错误的状态按位置挨个字符输出。 int idx1 = 0; int idx2 = 0; for (int i = 0; i < len3; ++i) { string t1, t2; int idx3 = idx1; int idx4 = idx2; // t1为字符串1在当前重复字符前的字符串 for (int m = idx1; m < len1; ++m) { if (str1[m] == substr[i]) { t1 = str1.substr(idx1, m - idx1); idx1 = m + 1; break; } } // t2为字符串2在当前重复字符前的字符串 for (int n = idx2; n < len2; ++n) { if (str2[n] == substr[i]) { t2 = str2.substr(idx2, n - idx2); idx2 = n + 1; break; } } // 根据不同情况处理 if (t1 == "" && t2 != "") { cout << "位置" << idx3 << "多出：" << t2 << endl; } else if (t1 != "" && t2 == "") { while (t1 != "") { cout << "位置" << idx3 << "缺少：" << t1[0] << endl; idx3++; t1 = t1.substr(1, t1.size() - 1); } } else if (t1 == "" && t2 == "") { } else { while (t1 != "") { cout << "位置" << idx3 << "错误，应为：" << t1[0] << endl; idx3++; t1 = t1.substr(1, t1.size() - 1); } } } // 对尾巴数据处理 if (idx1 < len1) { string tail = str1.substr(idx1, len1 - idx1); while (tail != "") { cout << "位置" << idx1 << "错误，应为：" << tail[0] << endl; idx1++; tail = tail.substr(1, 1); } } } int main() { std::string str1 = "1abcdefui"; std::string str2 = "abxcegfui"; cout << "字符串1：" << str1 << endl; cout << "字符串2：" << str2 << endl; // 获取最长重复子串（可不连续） string substr = getSubString(str1, str2); cout << "substring:" << substr << endl; // 比较字符串 compareString(str1, str2, substr); system("pause"); return 0; }
测试代码：
