数据结构与算法之最长公共子串

大家好，欢迎来到IT知识分享网。

最长公共子串问题是指给定两个字符串S1和S2，求它们的公共子串中最长的那一个。其实就是求两个字符串的最长重复子串。

最朴素的算法就是枚举S1和S2的每一对子串，然后判断它们是否相等，时间复杂度是O(n^3)。但是这种算法效率太低，无法满足实际需求。

一般采用动态规划的思想进行求解，令dp[i][j]表示以S1的前i个字符和S2的前j个字符为结尾的公共子串的长度，当S1[i]=S2[j]时，dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]=0。最后找出dp[i][j]的最大值即可。

时间复杂度为O(n^{2)。不过需要注意的是，由于dp数组是一个二维数组，所以空间复杂度也是O(n}2)，如果字符串比较长的话，可能会造成内存溢出的问题。可以采用滚动数组的方法来优化空间复杂度，将二维数组转化为一维数组。

一、C 实现 最长公共子串 及代码详解

最长公共子串是指两个字符串中相同的连续子串中，最长的那一个。例如，“abcmnopq” 和 “xyzmnopqa” 的最长公共子串是 “mnopq”。

下面是 C 语言实现最长公共子串的一个示例代码：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 100 char *lcs(char *str1, char *str2) { int mat[N][N] = {0}; int len1 = strlen(str1), len2 = strlen(str2); int max_len = 0, max_end = 0; for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { if (str1[i] == str2[j]) { if (i == 0 || j == 0) { mat[i][j] = 1; } else { mat[i][j] = mat[i-1][j-1] + 1; } if (mat[i][j] > max_len) { max_len = mat[i][j]; max_end = i; } } } } char *lcs_str = (char*)malloc((max_len+1)*sizeof(char)); strncpy(lcs_str, str1+max_end-max_len+1, max_len); lcs_str[max_len] = '\0'; return lcs_str; } int main() { char str1[N], str2[N]; printf("Input two strings:\n"); scanf("%s %s", str1, str2); char *lcs_str = lcs(str1, str2); printf("The longest common substring is: %s\n", lcs_str); free(lcs_str); return 0; } 

下面是代码的详解：

1. 第 4 行定义了一个宏，用于指定字符串的最大长度。
2. 第 6 行开始定义了一个名为 lcs 的函数，该函数接受两个字符串作为参数，返回最长公共子串。
3. 第 7 行定义了一个二维数组 mat，用来存储两个字符串的公共子串的长度。
4. 第 10 至第 12 行初始化变量以及记录最长公共子串的长度和结尾位置。
5. 第 13 至第 22 行使用两重循环遍历两个字符串，比较其字符是否相同，如果相同，则将其在 mat 中对应的元素赋值为前一个对角元素加一，即 $ma{t}_{i,j}=ma{t}_{i-1,j-1}+1$；此外，如果当前公共子串长度大于之前记录的最大长度，则更新最大长度和结尾位置。
6. 第 24 至第 27 行分配一段内存，该内存用于存储最长公共子串。由于 strncpy 函数不会自动将字符串结尾符添加到复制的字符串末尾，因此需要手动添加结尾符。
7. 最后使用 free 函数释放分配的内存。

该算法的时间复杂度为 $O(n^2)$，其中 $n$ 为两个字符串中最长的那个。

二、C++ 实现 最长公共子串 及代码详解

最长公共子串问题是指找出两个字符串中相同的最长子串。该问题可以使用动态规划算法解决。具体实现如下：

假设有两个字符串s1和s2，它们的长度分别为n和m。令dp[i][j]表示以s1[i]和s2[j]结尾的公共子串的最长长度。则有以下状态转移方程：

最终，要找到最长公共子串的长度，只需要遍历dp数组中的所有元素，找到其中最大值即可。

下面是该算法的完整代码实现：

#include <iostream> #include <cstring> using namespace std; const int N = 1000; char s1[N], s2[N]; int dp[N][N]; int main() { 
    cin >> s1 + 1 >> s2 + 1; // 从1开始存储字符串，方便后续的状态转移 int n = strlen(s1 + 1), m = strlen(s2 + 1); int ans = 0; // 最长公共子串的长度 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s1[i] == s2[j]) { 
    dp[i][j] = dp[i-1][j-1] + 1; ans = max(ans, dp[i][j]); // 更新最长公共子串的长度 } else dp[i][j] = 0; // 不相等，最长公共子串的长度为0 cout << ans << endl; return 0; } 

该算法的时间复杂度为$O(nm)$，其中n和m分别为两个字符串的长度。

三、Java 实现 最长公共子串 及代码详解

最长公共子串是两个或多个字符串中共有的最长的子串。

Java实现最长公共子串可以采用动态规划的方法。具体步骤如下：

1. 构造一个二维数组dp[i][j]，表示字符串s1以第i个字符结尾，字符串s2以第j个字符结尾的最长公共子串长度。
2. 初始化dp数组，即当i=0或j=0时，dp[i][j]均为0。
3. 递推计算dp[i][j]的值，当s1[i]=s2[j]时，dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=0。
4. 在递推的过程中，记录出现最大值的时候的索引，即可求得最长公共子串。

下面是Java代码实现：

public static String longestCommonSubstring(String s1, String s2) { 
    int m = s1.length(), n = s2.length(); int[][] dp = new int[m][n]; int maxLength = 0, endIndex = 0; // 初始化dp数组 for (int i = 0; i < m; i++) { 
    Arrays.fill(dp[i], 0); } // 递推计算dp数组 for (int i = 0; i < m; i++) { 
    for (int j = 0; j < n; j++) { 
    if (s1.charAt(i) == s2.charAt(j)) { 
    if (i == 0 || j == 0) { 
    dp[i][j] = 1; } else { 
    dp[i][j] = dp[i - 1][j - 1] + 1; } } // 更新最大值及索引 if (dp[i][j] > maxLength) { 
    maxLength = dp[i][j]; endIndex = i; } } } return s1.substring(endIndex - maxLength + 1, endIndex + 1); } 

在这个代码中，substr方法用于截取子串，Arrays.fill方法用于填充数组。

上述代码是时间复杂度为O(mn)的动态规划算法实现最长公共子串的方式。