longest common substring

题目地址：
http://www.programcreek.com/2015/04/longest-common-substring-java/

题目：
In computer science, the longest common substring problem is to find the longest string that is a substring of two or more strings.

解题思路：
Given two strings a and b, let dp[i][j] be the length of the common substring ending at a[i] and b[j]. 还有一种解法是用suffix tree，比较复杂，但是时间复杂度是O(m + n). 这里是suffix tree的链接：https://www.dropbox.com/s/x8rjlsjkg78bbso/Project%202.pdf?dl=0. code 链接：https://www.dropbox.com/sh/oeg1c5eawf6l7of/AAAw2XQ8aTEwbNNF5bxKYwika?dl=0

代码：

public class LongestCommonSubstring {

    public static int longestcommonsubstring(String s1, String s2){
        if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
            return 0;
        }
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m][n];
        int max = 0;
        for(int i = 0 ; i <= m - 1; i++){
            for(int j = 0; j <= n - 1; j++){
                if(s1.charAt(i) == s2.charAt(j)){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }
                    else{
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max;
    }
    public static void main(String[] args){
        LongestCommonSubstring longestCommonSubstring = new LongestCommonSubstring();
        String s1 = "substring";
        String s2 = "prevstring";
        int rst = longestCommonSubstring.longestcommonsubstring(s1, s2);
        System.out.println(rst);
    }
}