Length N Common Substring

题目：

找两个字符串长度为N以上的共同字串。

解题思路：

用dynamic programming来做。dp[i, j] is the length of the longest common string ending at i and j respectively in 2 strings.

代码：

public class LengthNCommonSubstring {

    public List<String> getCommonSubstringWithLengthN(String s1, String s2, int N){
        List<String> rst = new ArrayList<>();
        if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
            return rst;
        }
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m][n];
        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;
                    }
                    if(dp[i][j] >= N){
                        int start = i - N + 1;
                        String s = s1.substring(start, i + 1);
                        rst.add(s);
                    }
                }
            }
        }
        return rst;
    }
    public static void main(String[] args){
        LengthNCommonSubstring lengthNCommonSubstring = new LengthNCommonSubstring();
        String s1 = "substring";
        String s2 = "prevstring";
        List<String> rst = lengthNCommonSubstring.getCommonSubstringWithLengthN(s1, s2, 4);
        System.out.println(rst);
    }
}