[动态规划]BM66 最长公共子串-中等

网络安全邮递员 lv.1

发布时间：2022-10-21 00:31:08 290

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串题目保证str1和str2的最长公共子串存在且唯一。

数据范围：

要求：空间复杂度，时间复杂度

示例1

输入：

"1AB2345CD","12345EF"

返回值：

"2345"

备注：

1 1≤∣str1∣,∣str2∣≤5000

题解

思路：

1. 我们可以用表示在str1中以第个字符结尾在str2中以第个字符结尾时的公共子串长度
2. 遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i - 1][j - 1] + 1dp[i][j]=dp[i−1][j−1]+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
3. 每次更新后，我们维护最大值，并更新该子串结束位置
4. 最后根据最大值结束位置即可截取出子串

代码如下：

#include <bits/stdc++.h>

using namespace std;

string LCS(string str1, string str2)
{
  if (str1.empty() || str2.empty())
  {
    return "";
  }
  int end_pos = 0;// 最大长度结束标志位
  int max_len = 0;// 最大长度，和 end_pos 一起用来返回最终的结果
  std::vector<std::vector<int>> dp(str1.size() + 1, std::vector<int>(str2.size() + 1, 0));
  for (int i = 1; i <= str1.size(); i++)
  {
    for (int k = 1; k <= str2.size(); ++k)
    {
      if (str1[i - 1] == str2[k - 1])
      {
        dp[i][k] = dp[i - 1][k - 1] + 1;
        if (max_len < dp[i][k])
        {
          end_pos = i;
          max_len = dp[i][k];
        }
      }
      else
      {
        dp[i][k] = 0;
      }
    }
  }
  return str1.substr(end_pos - max_len, max_len);
}

文章来源： https://blog.51cto.com/u_6650004/5396612

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。