LintCode-Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Note

The characters in substring should occur continiously in original string. This is different with subsequnce.

Solution:

 1 public class Solution {
 2     /**
 3      * @param A, B: Two string.
 4      * @return: the length of the longest common substring.
 5      */
 6     public int longestCommonSubstring(String A, String B) {
 7         int lenA = A.length();
 8         int lenB = B.length();
 9         if (lenA==0 || lenB ==0 ) return 0;
10 
11         int[][] lcs = new int[lenA+1][lenB+1];
12         for (int i=0;i<=lenA;i++) lcs[i][0] = 0;
13         for (int i=0;i<=lenB;i++) lcs[0][i] = 0;
14 
15         int res = 0;
16         for (int i=1;i<=lenA;i++)
17             for (int j=1;j<=lenB;j++)
18                 if (A.charAt(i-1)==B.charAt(j-1)){
19                     lcs[i][j]=lcs[i-1][j-1]+1;
20                     if (lcs[i][j]>res) res = lcs[i][j];
21                 } else lcs[i][j]=0;
22 
23         return res;
24     }
25 }