最长的公共子字符串

给定 2 个字符串 str1 和 str2，我们必须找到它们之间最长公共子字符串的长度。

例子

输入：X =abcdxyz，y =xyzabcd 输出：4

最长的公共子字符串是 abcd，长度为 4。

输入：X =zxabcdezy，y =yzabcdezx 输出：6

最长的公共子字符串是 abcdez，长度为 6。

用 Java 实现

public int getLongestCommonSubstring(String str1,String str2){
        int arr[][] = new int[str2.length()+1][str1.length()+1];
        int max = Integer.MIN_VALUE;
        for(int i=1;i<=str2.length();i++){
            for(int j=1;j<=str1.length();j++){
                if(str1.charAt(j-1) == str2.charAt(i-1)){
                    arr[i][j] = arr[i-1][j-1]+1;
                    if(arr[i][j]>max)
                        max = arr[i][j];
                }
                else
                    arr[i][j] = 0;
            }
        }
        return max;
    }

时间复杂性

O（m * n 个）