LintCode-Longest Common Substring

 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 }