Given two strings, find the longest common substring.

Return the length of it.

Example

Given A = “ABCD”, B = “CBCE”, return 2.

Note

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

Challenge

O(n x m) time and memory.

Solution: Dynamic Programming

public int longestCommonSubstring(String A, String B) { int[][] lcs = new int[A.length()][B.length()]; int max = 0; for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (A.charAt(i) == B.charAt(j)) { if (i == 0 || j == 0) { lcs[i][j] = 1; } else { lcs[i][j] = lcs[i - 1][j - 1] + 1; } } if (lcs[i][j] > max) { max = lcs[i][j]; } } } return max; }