给出两个字符串，找到最长公共子串，并返回其长度。
子串的字符应该连续的出现在原字符串中，这与子序列有所不同。
您在真实的面试中是否遇到过这个题？ Yes 样例给出A=“ABCD”，B=“CBCE”，返回 2
标签相关题目
首先想到的是暴力解法，复杂度是O(N^2*M^2),时间复杂度过高动态规划：String S1,S2,C[ i ]][ j ] 表示以S1[ i ]和S[ j ]结尾的的相同子串的包含S[ i ]的最大长度既是S1.substring(0,i)和s2.substring(0,j)的相同子串的最大长度， 若char S1[ i ] = char S2[ j ] ,C[ i ] [ j ] = C[ i-1 ][ j-1 ]+1,否则C[ i ][ j ] = 0 /** * @param A, * B: Two string. * @return: the length of the longest common substring. * */ public int longestCommonSubstring(String A, String B) { // write your code here if (A == null || B == null || A.length() == 0 || B.length() == 0) { return 0; } int m = A.length(); int n = B.length(); int maxLongLength = -1; int c[][] = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1)) { c[i][j] = c[i - 1][j - 1] + 1; } else { c[i][j] = 0; } maxLongLength = Math.max(maxLongLength, c[i][j]); } } return maxLongLength; }
