C++求解最长公共子串问题 |21xrx.com

C++求解最长公共子串问题

2023-07-01 14:10:36 深夜i -- --

C++ 最长公共子串问题求解

最长公共子串问题是指找出两个字符串中最长的共同的子串，是计算机领域中一个经典的算法问题。解决这个问题有多种方法，其中一种就是使用C++语言来实现。下面将介绍如何使用C++语言求解最长公共子串问题。

首先，我们需要定义两个字符串，假设分别为str1和str2。然后，我们可以创建一个二维数组来储存两个字符串的匹配情况。假设我们定义的数组为match，那么match[i][j]表示str1中第i个字符和str2中第j个字符是否匹配。为了方便起见，将字符串下标从1开始计算。则match[i][j]的值可以根据如下规则计算：

如果str1[i] == str2[j]，则match[i][j] = match[i-1][j-1] + 1

否则，match[i][j] = 0

这种方法被称为动态规划。它的思想是从小问题转移到大问题，每步都是基于上一步的解，因此不需要重复计算。

接下来，我们需要找到match数组中最大的值，这个值就是最长公共子串的长度。然后，我们可以根据这个长度，从原来的字符串中提取出最长公共子串。

下面是一个使用C++语言实现求解最长公共子串问题的例子：


#include <iostream>
#include <string>
using namespace std;
int main() {
  string str1 = "abcde";
  string str2 = "ababcde";
  int match[6][8] = {0}; // 初始化二维数组
  int max_len = 0; // 最长公共子串的长度
  int max_index = 0; // 最长公共子串的起始下标
  // 计算二维数组中每个元素的值
  for (int i = 1; i <= str1.length(); i++) {
    for (int j = 1; j <= str2.length(); j++) {
      if (str1[i-1] == str2[j-1]) {
        match[i][j] = match[i-1][j-1] + 1;
        if (match[i][j] > max_len) {
          max_len = match[i][j];
          max_index = i - max_len; // 记下最长公共子串的起始下标
        }
      }
      else {
        match[i][j] = 0;
      }
    }
  }
  // 从原字符串中提取最长公共子串
  string result = str1.substr(max_index, max_len);
  cout << "最长公共子串为: " << result << endl;
  return 0;
}

上面的代码将输出最长公共子串为 "abc"。这就是使用C++语言求解最长公共子串问题的过程。由此可见，使用C++语言来求解这个问题并不难，只需要遵循动态规划的思路即可。

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

下一篇: Node.js和PHP的比较

评论区

()

相似文章