最长公共子串是指在两个字符串中，连续出现的最长子串，例如字符串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++代码实现最长公共子串的两种方法：暴力枚举法和动态规划。虽然暴力枚举法的时间复杂度较高，但代码实现较为简单，不需要额外的空间，适合处理小规模的字符串问题；动态规划方法的时间复杂度较低，但需要额外的空间，代码实现较为复杂，适合处理中等规模的字符串问题。在实际应用中，可以根据数据规模和代码实现难度选择合适的方法。

相似文章
• C++求解最长公共子串
  最长公共子串问题是计算机科学中一个经典的问题，也是很多算法题目中经常考察的一个问题。这个问题的求解能够对很多方面产生帮助，比如字符串比较，文本相似度计算等等。
  
  
• C++代码：求解最长公共子串
  最长公共子串是指在两个字符串中都出现过的最长的子字符串。这是一个经典的字符串问题，我们可以用动态规划的思想来解决它。
  
  
• C++代码：求解最长公共子串
  最长公共子串是指在两个字符串中同时出现的最长连续子串。求解最长公共子串对于许多字符串匹配问题都非常重要。在这篇文章中，我们将介绍如何使用C++代码来求解最长公共子串。
  
  
• C++实现最长公共子串算法
  最长公共子串（Longest
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政