最長的公共子字串

給定 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 個）