最长公共子串

原题链接：https://www.lintcode.com/problem/79

题目

给出两个字符串，找到最长公共子串，并返回其长度。

子串的字符应该连续的出现在原字符串中，这与子序列有所不同。

样例

样例 1：

输入：

字符串A = "ABCD"
字符串B = "CBCE"

输出：

解释：

最长公共子串是 “BC”

样例 2：

输入：

字符串A = "ABCD"
字符串B = "EACB"

输出：

解释：

最长公共子串是 ‘A’ 或 ‘C’ 或 ‘B’

挑战

O(n x m) 时间复杂度和空间复杂度

问题分析

1.设计状态

本题与最长公共子序列不同，子串要求要是连续的，而子序列不要求连续

如果已经会了最长公共子序列，那么这道题就比较容易了

首先还是先进行分析，然后设计状态，求A[i]与B[i]之间的公共子串，也分为两种情况

A[i] = B[i], 如果当前两个字符串比较的字符相同，那么就转移到他们前一个字符再进行比较
A[i] != B[i],如果不相同，那么就不同构成公共子串，所以直接为0

通过分析，就可以设计状态了，还是用最简单的二维表进行比较，dp[i][j] 表示A字符串前i个字符与B字符串前j个字符的公共子串

2. 状态转移方程

$\begin{cases} dp[i][j] = dp[i - 1][j - 1] + 1 & A[i] = B[j] \\ dp[i][j] = 0 & A[i] \ne B[j] \end{cases}$

3.设定初始状态

当A字符串为空串时，A与B的公共子串为0，同理B字符串为空时，也是一样为0

4.执行状态转移

在这里插入图片描述

根据公式可以很容易的就画出这幅图来，从第二行开始进行比较，如果遇到了相同的字符（图中红色圈圈标出来的）就进行状态转移，去找dp[i-1][j-1]的值，在其基础上+1，如果不相同，就直接设为0

通过比较可以看出来，两个字符串的最大公共子串长度为3，那么只要再遍历一趟二维数组，就可以求出最大值了，也可以在开始进行状态转移的过程中就进行最大值的比较，设定一个变量mx表示当前数组中最大值，每次更新dp[i][j]时，都与之比较大小。

代码

C++

class Solution {
public:/*** @param A: A string* @param B: A string* @return: the length of the longest common substring.*/int longestCommonSubstring(string &A, string &B) {// write your code hereint lena = A.size();int lenb = B.size();int len = max(lena, lenb);vector<int> tmp(len + 1, 0);// 初始化状态vector<vector<int>> dp(len + 1, tmp);int _max = 0;for (int i = 1; i <= lena; i++) {for (int j = 1; j <= lenb; j++) {// 状态转移if (A[i - 1] == B[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;// 求最大值_max = max(_max, dp[i][j]);} else {dp[i][j] = 0;}}}// 返回最终的解return _max;}
};

java

public class Solution {/*** @param A: A string* @param B: A string* @return: the length of the longest common substring.*/public int longestCommonSubstring(String A, String B) {// write your code herechar[] a = A.toCharArray();char[] b = B.toCharArray();int lena = A.length();int lenb = B.length();if (lena == 0 || lenb == 0) return 0;int len = Math.max(lena, lenb);int[][] dp = new int[len + 1][len + 1];// 初始化状态for (int i = 0; i < lena; i++) {dp[i][0] = 0;}for (int j = 0; j < lenb; j++) {dp[0][j] = 0;}int _max = 0;for (int i = 1; i <= lena; i++) {for (int j = 1; j <= lenb; j++) {// 状态转移if (a[i - 1] == b[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;// 保存最大值_max = Math.max(_max, dp[i][j]);} else {dp[i][j] = 0;}}}// 返回最终的解return _max;}
}