当前位置: 首页 > news >正文

最长公共子串问题

最长公共子串问题

在字符串匹配和文本处理问题中,最长公共子串问题(Longest Common Substring, LCS)是一个经典的问题。给定两个字符串,找出它们的最长公共子串。子串要求字符在原字符串中的位置必须连续,且在两个字符串中完全一致

在本文中,我们将介绍如何使用动态规划(Dynamic Programming, DP)结合二维数组来高效地解决这一问题。


1. 问题定义

给定两个字符串 str1 \text{str1} str1 str2 \text{str2} str2,我们要找到它们的最长公共子串的长度和内容。

例如:

  • 输入:str1 = "abcdef"str2 = "abfdef"
  • 输出:最长公共子串为 "def",长度为 3

2. 思路分析

最长公共子串问题的解法之一是通过动态规划来记录两个字符串之间的匹配情况。我们使用一个二维数组来记录每个位置匹配的子串长度,然后在整个表格中找到最大的匹配长度,即为最长公共子串。

动态规划定义

dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子串的长度。转移方程如下:

  • 如果 str1[i-1] == str2[j-1],那么 dp[i][j] = dp[i-1][j-1] + 1
  • 如果 str1[i-1] != str2[j-1],则 dp[i][j] = 0

该动态规划表格的更新逻辑是:若两个字符匹配,则公共子串的长度增加;若不匹配,则该位置的公共子串长度为零。


3. 状态转移方程

根据上述分析,状态转移方程可以写为:

d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] + 1 , if  s t r 1 [ i − 1 ] = = s t r 2 [ j − 1 ] 0 , if  s t r 1 [ i − 1 ] ≠ s t r 2 [ j − 1 ] dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } str1[i-1] == str2[j-1] \\ 0, & \text{if } str1[i-1] \neq str2[j-1] \end{cases} dp[i][j]={dp[i1][j1]+1,0,if str1[i1]==str2[j1]if str1[i1]=str2[j1]

边界条件是:当 ( i = 0 ) 或 ( j = 0 ) 时,dp[i][j] = 0,因为没有字符可以比较。

4. 示例演示

str1 = "abcde"str2 = "abfde" 为例,我们构造 dp 表格如下:

abfde
000000
a010000
b002000
c000000
d000010
e000002

在这个表格中,最长公共子串的长度为 2(即 de),可以通过遍历 dp 表格找到最长公共子串的长度和位置。


5. 代码实现

Python代码:

import os
import sys# 请在此输入您的代码def init_arr(n,m):return [[0]*m for i in range(n)]def print_arr(arr):for i in range(len(arr)):for j in range(len(arr[0])):print(arr[i][j], end=' ')print()def solve(str1,str2,dp):max_str = Nonemax_len = 0for i in range(1,len(str1)):for j in range(1,len(str2)):if str1[i] != str2[j]: # 重新计数最长字串dp[i][j] = 0else: dp[i][j] = dp[i-1][j-1] + 1if dp[i][j] > max_len: #不仅当前下标对应字符相等且字串在不断的增长max_len = dp[i][j]if max_str is None:max_str = str1[i]else:max_str += str1[i]return max_len, max_strs1, s2 = input(), input()
s1 = ' '+s1
s2 = ' '+s2
dp = init_arr(len(s1)+1,len(s2)+1)
max_len, max_str = solve(s1,s2,dp)
# print(max_len,max_str)
# print_arr(dp)
print(max_str)

C++代码实现

#include<bits/stdc++.h>
using namespace std;const int max_len = 1024;
int dp[max_len][max_len];char* solve(char*, char*);int main(){
//	string s1,s2;
//	cin>>s1>>s2;
//	cout<<s1<<s2;char* str1 = (char *)malloc(sizeof(char) * max_len);char* str2 = (char *)malloc(sizeof(char) * max_len); cin>>str1>>str2;char* res = solve(str1,str2);cout<<res;return 0;
} char* solve(char* str1,char* str2){int n,m;n = strlen(str1);m = strlen(str2);char* res = (char*)malloc(sizeof(char) * max_len);int max_len = 0;int idx = 0;for(int i=1;i<n;i++){for(int j=1;j<n;j++){if (str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1]+1;if(dp[i][j]> max_len){max_len = dp[i][j];res[idx++] = str1[i-1];}}else{dp[i][j] = 0;}}}res[idx++] = '\0'; return res;
}

6. 代码解释

  1. 初始化 DP 表格:二维数组 dp 的大小为 (len1 + 1) * (len2 + 1),初始化为 0。
  2. 填充 DP 表格:通过双重循环,若 str1[i-1]str2[j-1] 匹配,则 dp[i][j] = dp[i-1][j-1] + 1;否则 dp[i][j] = 0
  3. 记录最大长度和结束位置:在每次更新 dp[i][j] 时,若新长度超过当前最大长度,则更新最大长度 max_length 和结束位置 end_pos
  4. 提取最长公共子串:根据 end_posmax_length 提取最长公共子串。

7. 示例输出

str1 = "abcdef"
str2 = "abfdef"
最长公共子串长度:   # 输出: 3
最长公共子串内容:   # 输出: def

8. 时间和空间复杂度分析

  • 时间复杂度:由于我们使用了两个嵌套循环来填充 dp 表格,因此时间复杂度为 O ( m × n ) O(m \times n) O(m×n),其中 m m m n n n 分别是 str1str2 的长度。
  • 空间复杂度:需要一个 ( m + 1 ) × ( n + 1 ) (m+1) \times (n+1) (m+1)×(n+1) 的二维数组 dp 来存储中间状态,因此空间复杂度也为 O ( m × n ) O(m \times n) O(m×n)

总结

通过使用动态规划解决最长公共子串问题,我们可以在相对较短的时间内找到两个字符串的最长公共子串。此方法使用二维数组存储每一步的中间状态,从而避免重复计算,大大提高了效率。


http://www.mrgr.cn/news/61742.html

相关文章:

  • Windows Server NTFS磁盘变RAM的处理过程
  • Vue.js(2) 基础:指令与功能概览
  • 在 Vue 中如何自动导入项目中的 less 和 scss 变量和文件
  • 力扣刷题(sql)--零散知识点(2)
  • Spring Boot 中应用单元测试(UT):结合 Mock 和 H2 讲解和案例示范
  • C++研发笔记10——C语言程序设计初阶学习笔记8
  • 【Linux系统编程】第三十九弹---探索信号处理的奥秘:阻塞信号与sigset_t的深入剖析及实战
  • BUUCTF靶场Misc练习
  • yarn 下载安装、下载依赖、通过 vscode 运行服务(Windows11)
  • 企业如何提高外呼电话接通率?申请来电名片需要什么材料?
  • 数据驱动的智能化投资:民锋金融科技创新的策略分析
  • Linux权限管理中的文件权限与目录权限
  • 引领数字未来:通过企业架构推动数字化转型的策略与实践
  • [原创](Modern C++)现代C++的数据拷贝实用技术std::copy()与std::copy_if()
  • Photoshop图像算法(十)(代码在每个原理后面)
  • linux重定向函数dup、dup2函数
  • 智慧水坝和智慧水闸是水务管理的标配,看看别人家咋做的。
  • 锐捷配置sshhe telnet登录。
  • 普通人适合做大模型吗?过程中会发生什么潜在的挑战?
  • FragmentActivity理解
  • C++入门基础知识131—【关于C 库函数 - localtime()】
  • 基于PP-OCR和ErnieBot的视频字幕提取和问答助手
  • 【总结】空间景观指标
  • DAY66WEB 攻防-Java 安全SPEL 表达式SSTI 模版注入XXEJDBCMyBatis 注入
  • 【C++】类和对象(五):拷贝构造
  • 深入浅出Python网络爬虫:从入门到实战(附爬虫实战代码)