C++代码实现最长公共子串 |21xrx.com

C++代码实现最长公共子串

2023-07-11 18:03:41 深夜i -- --

C++ 最长公共子串代码实现

最长公共子串是指在两个字符串中，连续出现的最长子串，例如字符串A为"abacdfgdcabae"，字符串B为"abacdefgdcaba"，则其最长公共子串为"dgdcaba"。在许多实际应用场景中，需要求解最长公共子串，例如字符串匹配、比较DNA序列等。下面介绍C++代码实现最长公共子串的方法。

1. 暴力枚举法

暴力枚举法是最简单的方法，即对两个字符串进行穷举匹配，找出最长的公共子串。具体实现如下：


string longest_common_substring(string s1, string s2) {
  int len1 = s1.length(), len2 = s2.length();
  string res;
  for (int i = 0; i < len1; i++) {
    for (int j = 0; j < len2; j++) {
      int k = 0;
      while (i + k < len1 && j + k < len2 && s1[i + k] == s2[j + k]) {
        k++;
      }
      if (k > res.length()) {
        res = s1.substr(i, k);
      }
    }
  }
  return res;
}

该算法的时间复杂度为$O(n^3)$，不适合处理大规模的字符串问题。

2. 动态规划

动态规划是解决最长公共子串问题的常用方法。具体思路是通过构建一个二维数组dp[i][j]，记录两个字符串公共子串的长度，其中i表示字符串A中的第i个字符，j表示字符串B中的第j个字符。如果s1[i] == s2[j]，则dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。在计算过程中，记录最长的公共子串即可。


string longest_common_substring(string s1, string s2) {
  int len1 = s1.length(), len2 = s2.length();
  vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
  int max_len = 0, max_index = 0;
  for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
      if (s1[i - 1] == s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        if (dp[i][j] > max_len) {
          max_len = dp[i][j];
          max_index = i - max_len;
        }
      }
    }
  }
  return s1.substr(max_index, max_len);
}

该算法的时间复杂度为$O(n^2)$，适合处理中等规模的字符串问题。

总结

本文介绍了C++代码实现最长公共子串的两种方法：暴力枚举法和动态规划。虽然暴力枚举法的时间复杂度较高，但代码实现较为简单，不需要额外的空间，适合处理小规模的字符串问题；动态规划方法的时间复杂度较低，但需要额外的空间，代码实现较为复杂，适合处理中等规模的字符串问题。在实际应用中，可以根据数据规模和代码实现难度选择合适的方法。

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

下一篇: C++中的取模运算

评论区

()

相似文章