最长公共子串问题

最长公共子串问题

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

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

---

1. 问题定义

给定两个字符串 $\text{str1}$ 和 $\text{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. 状态转移方程

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

$dp[i][j]=\{\begin{array}{ll}dp[i-1][j-1]+1,& \text{if }str1[i-1]==str2[j-1]\\ 0,& \text{if }str1[i-1]\ne str2[j-1]\end{array}$

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

4. 示例演示

以 str1 = "abcde" 和 str2 = "abfde" 为例，我们构造 dp 表格如下：

		a	b	f	d	e
	0	0	0	0	0	0
a	0	1	0	0	0	0
b	0	0	2	0	0	0
c	0	0	0	0	0	0
d	0	0	0	0	1	0
e	0	0	0	0	0	2

在这个表格中，最长公共子串的长度为 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_pos 和 max_length 提取最长公共子串。

7. 示例输出

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

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

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

---

总结

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