Longest Common Substring

Question

Problem Statement

Given two strings, find the longest common substring.

Return the length of it.

Notice

The characters in substring should occur continuously in original string. This is different with subsequence.

Example

Given A = "ABCD", B = "CBCE", return 2.

Challenge **

O(n x m) time and memory.

题解1 - 暴力枚举

Python

class Solution:
# @param A, B: Two string.
# @return: the length of the longest common substring.
def longestCommonSubstring(self, A, B):
if not (A and B):
return 0

lcs = 0
for i in range(len(A)):
for j in range(len(B)):
lcs_temp = 0
while (i + lcs_temp < len(A) and
j + lcs_temp < len(B) and
A[i + lcs_temp] == B[j + lcs_temp]):
lcs_temp += 1
# update lcs
if lcs_temp > lcs:
lcs = lcs_temp
return lcs


C++

class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
if (A.empty() || B.empty()) {
return 0;
}

int lcs = 0;
for (int i = 0; i < A.length(); ++i) {
for (int j = 0; j < B.length(); ++j) {
int lcs_temp = 0;
while ((i + lcs_temp < A.length()) &&
(j + lcs_temp < B.length()) &&
(A[i + lcs_temp] == B[j + lcs_temp])) {
++lcs_temp;
}
// update lcs
if (lcs_temp > lcs) lcs = lcs_temp;
}
}

return lcs;
}
};


Java

public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
if ((A == null || A.isEmpty()) ||
(B == null || B.isEmpty())) {
return 0;
}

int lcs = 0;
for (int i = 0; i < A.length(); i++) {
for (int j = 0; j < B.length(); j++) {
int lcs_temp = 0;
while (i + lcs_temp < A.length() &&
j + lcs_temp < B.length() &&
A.charAt(i + lcs_temp) == B.charAt(j + lcs_temp)) {
lcs_temp++;
}
// update lcs
if (lcs_temp > lcs) lcs = lcs_temp;
}
}

return lcs;
}
}


源码分析

1. 异常处理，空串时返回0.
2. 分别使用ij表示当前遍历的索引处。若当前字符相同时则共同往后移动一位。
3. 没有相同字符时比较此次遍历的lcs_templcs大小，更新lcs.
4. 返回lcs.

题解2 - 动态规划

Python

class Solution:
# @param A, B: Two string.
# @return: the length of the longest common substring.
def longestCommonSubstring(self, A, B):
if not (A and B):
return 0

n, m = len(A), len(B)
f = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
for j in range(m):
if A[i] == B[j]:
f[i + 1][j + 1] = 1 + f[i][j]

lcs = max(map(max, f))
return lcs


C++

class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
if (A.empty() || B.empty()) {
return 0;
}

int n = A.length();
int m = B.length();
vector<vector<int> > f = vector<vector<int> >(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (A[i] == B[j]) {
f[i + 1][j + 1] = 1 + f[i][j];
}
}
}

// find max lcs
int lcs = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (f[i][j] > lcs) lcs = f[i][j];
}
}

return lcs;
}
};


Java

public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
if ((A == null || A.isEmpty()) ||
(B == null || B.isEmpty())) {
return 0;
}

int n = A.length();
int m = B.length();
int[][] f = new int[n + 1][m + 1];

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A.charAt(i) == B.charAt(j)) {
f[i + 1][j + 1] = 1 + f[i][j];
}
}
}

// find max lcs
int lcs = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (f[i][j] > lcs) lcs = f[i][j];
}
}

return lcs;
}
}


源码分析

1. 异常处理
2. 列出状态转移方程，关键处在于以 (i,j) 结尾的两个字符串

powered by