Longest Common Substring

题目
Given two strings, find the longest common substring.

Return the length of it.

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

答案

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
     
     /*
            f[i][j] := LCS ending in A[i] and B[j]
        
            if A[i] == A[j]
            f[i][j] = f[i - 1][j - 1] + 1
            
            if A[i] != A[j] 
            f[i][j] = 0
        */
        
    public int longestCommonSubstring(String AA, String BB) {
        int m = AA.length(), n = BB.length();
        if(m == 0 || n == 0) return 0;
        char[] A = AA.toCharArray();
        char[] B = BB.toCharArray();
        
        int[][] f = new int[m][n];
        int max = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) {
                    f[i][j] = (A[i] == B[j])? 1:0;
                    max = Math.max(max, f[i][j]);
                    continue;
                }
                if(A[i] == B[j]) {
                    f[i][j] = 1 + f[i - 1][j - 1];
                }
                else {
                    f[i][j] = 0;
                }
                max = Math.max(max, f[i][j]);
            }
        }
        return max;
    }
}