C++实现最长公共子串算法 |21xrx.com

C++实现最长公共子串算法

2023-06-20 21:13:35 深夜i -- --

C++ 最长公共子串算法实现

最长公共子串（Longest Common Substring）是一种经典的字符串匹配问题，其要求是在两个字符串中找到一个最长的公共子串。它在算法设计和字符串处理中有着广泛的应用。

C++语言是一种高效、强大的编程语言，它提供了许多字符串处理的函数和类，使得编写最长公共子串算法变得更加简单。下面我们来看一下如何使用C++实现最长公共子串算法。

首先，我们需要定义两个字符串，用来进行比较：


string str1 = "abcdefg";
string str2 = "abcdeyh";

接下来，我们通过两个嵌套循环来计算最长公共子串的长度。这个方法被称为动态规划，它的核心思想是将一个大问题拆分成多个小问题来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子串长度。


int maxLength = 0;
int len1 = str1.size(), len2 = str2.size();
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for (int i = 1; i <= len1; i++) {
  for (int j = 1; j <= len2; j++) {
    if (str1[i - 1] == str2[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
      maxLength = max(maxLength, dp[i][j]); //更新最长子串长度
    }
  }
}

不难发现，在每次循环中，我们比较的是两个字符串的当前字符是否相等。如果相等，则将dp[i][j]的值设置为dp[i-1][j-1]加1，否则，其值为0，表示此时没有公共子串。最后，我们输出maxLength即可得到最长公共子串的长度。

当然，我们也可以使用dp数组来计算具体的最长公共子串，如下所示：


string longestSubstring;
for (int i = 1; i <= len1; i++) {
  for (int j = 1; j <= len2; j++) {
    if (dp[i][j] == maxLength) {
      longestSubstring = str1.substr(i - maxLength, maxLength);
    }
  }
}

这段代码利用了substr函数来对字符串进行子串提取，从而得到具体的最长公共子串。

综上所述，使用C++实现最长公共子串算法并不难，只需要掌握基本的字符串处理函数和动态规划思想即可。该算法的时间复杂度为O(n^2)，在实际应用中具有一定的局限性，但在大多数情况下已足够满足需求。

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

下一篇: 《VC++书籍推荐》

评论区

()

相似文章