Java 代码实现查找两个字符串的最大公共子串长度 - 时间复杂度和空间复杂度分析

以下是查找两个字符串的最大公共子串长度的 Java 代码实现：

public static int findMaxCommonSubstringLength(String str1, String str2) {
    int[] prevRow = new int[str2.length() + 1];
    int[] currentRow = new int[str2.length() + 1];
    int maxLength = 0;

    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                currentRow[j] = prevRow[j - 1] + 1;
                maxLength = Math.max(maxLength, currentRow[j]);
            }
        }
        // 更新prevRow数组为currentRow数组
        for (int j = 0; j <= str2.length(); j++) {
            prevRow[j] = currentRow[j];
        }
    }

    return maxLength;
}

时间复杂度：

假设 str1 的长度为 m，str2 的长度为 n，那么外层循环会执行 m 次，内层循环会执行 n 次，所以总的时间复杂度为 O(m * n)。

空间复杂度：

算法中使用了两个长度为 str2.length() + 1 的数组 prevRow 和 currentRow，所以总的空间复杂度为 O(n)。