C++代码：求解最长公共子串 |21xrx.com

C++代码：求解最长公共子串

2023-07-05 10:01:06 深夜i 19 0

C++ 最长公共子串代码

最长公共子串是指在两个字符串中都出现过的最长的子字符串。这是一个经典的字符串问题，我们可以用动态规划的思想来解决它。

下面是一个C++代码示例来求解最长公共子串：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int longestCommonSubstring(string s1, string s2) {
  int n1 = s1.size(), n2 = s2.size();
  int dp[n1 + 1][n2 + 1];
  int max_len = 0; // 最长公共子串长度
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {
      if (s1[i - 1] == s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        max_len = max(max_len, dp[i][j]);
      }
      else {
        dp[i][j] = 0; // 不相等时需要重新计算
      }
    }
  }
  return max_len;
}
int main() {
  string s1 = "abcde";
  string s2 = "cdeabc";
  int res = longestCommonSubstring(s1, s2);
  cout << res << endl; // 3 (最长公共子串为 "cde")
  
  return 0;
}

动态规划中用到了一个二维数组 `dp` 来保存状态，`dp[i][j]` 表示以字符串 `s1` 的第 `i` 个字符和字符串 `s2` 的第 `j` 个字符为结尾的公共子串的长度。如果 `s1[i - 1]` 和 `s2[j - 1]` 相等，说明有一个新的字符可以加入到公共子串中，所以 `dp[i][j]` 就是 `dp[i - 1][j - 1]` 递推加上这个新的字符得到的长度。否则，如果 `s1[i - 1]` 和 `s2[j - 1]` 不相等，说明以 `s1[i - 1]` 和 `s2[j - 1]` 结尾的字符串不能构成公共子串，就需要重新计算公共子串的长度，赋值为0。

最终返回的结果就是 `dp` 数组中的最大值。

在这个例子中，最长公共子串为 "cde"，所以输出为 3。

总结起来，求解最长公共子串的问题可以使用动态规划来解决，通过构建状态转移方程以及保存状态的二维数组，可以高效地找出两个字符串中的最长公共子串。

上一篇: idea打包java可执行jar包

下一篇: C++ STL 内存管理

评论区

相似文章