题解 | #最长公共子串#

public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if (1 == str1.length() && 1 == str2.length()) {
            return str1.equals(str2) ? str1 : "";
        }
        if (str1.equals(str2)) {
            return str1;
        }
        // 定义一个整型变量，用于存放 str1 的长度
        int sl1 = str1.length();
        // 定义一个整型变量，用于存放 str2 的长度
        int sl2 = str2.length();
        // 定义一个整型变量，用于存放最短的字符串的长度
        int minl = sl1 < sl2 ? sl1 : sl2;
        // 定义一个整型变量，用于存放最长的字符串的长度
        int maxl = sl1 >= sl2 ? sl1 : sl2;
        // 定义一个字符串，用于存放长度最短的字符串
        String minStr = sl1 < sl2 ? str1 : str2;
        // 定义一个字符串，用于存放长度最大的字符串
        String maxStr = sl1 >= sl2 ? str1 : str2;
        // 定义一个整型数组，用于存放短的字符串中以某个字符为头的字符串中的最长公共子串
        int[] dp = new int[minl];
        // 定义一个整型变量，用于存放临时数据
        int val = 0;
        // 定义一个指针，偏移量
        int p = 0;
        for (int i = 0; i < minl; i++) {
            for (int j = 0; j < maxl; j++) {
                while (i + p < minl && j + p < maxl && maxStr.charAt(j + p) == minStr.charAt(i + p)) {
                    p++; // 向右偏移
                    val++;
                }
                p = 0; // 偏移量要重新置为 0
                dp[i] = Math.max(dp[i], val);
                val = 0;
            }
        }
        // 循环结束
        // 定义一个整型变量，用于存放索引
        int index = 0;
        // 定义一个整型变量，用于存放最大值
        int maxv = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (maxv < dp[i]) {
                maxv = dp[i];
                index = i;
            }
        }
        return minStr.substring(index, index + dp[index]);
    }
}