代码随想录算法训练营第九天 | 28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

即实现 KMP 算法。

class Solution {
    public int strStr(String text, String pattern) {
        int[] next = getNext(pattern);
        int start = 0, i = 0, j = 0;

        // 俩字符串从 0 开始匹配
        while (i < text.length() && j < pattern.length()) {
            // 相等，则同时前进，匹配下一个
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                // 不相等，则模式串的下标回退，文本串的下标不动
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    // 模式串都退到最初位置了也不相等，那么 i 前进，重新开始匹配
                    i++;
                }
            }
        }

        // 当模式串遍历完了，说明找到匹配的位置了，计算出下标
        if (j == pattern.length()) {
            return i - pattern.length();
        } else {
            return -1;
        }
    }

    public int[] getNext(String pattern) {
        char[] str = pattern.toCharArray();
        // next 用来模式串下标的回溯
        // next[i] 即表示 i 及其之前的字符串中最长公共前后缀中字符的数量
        // 也表示回溯时的下标，即模式串在第 j 个位置不匹配，则 j 要回溯到 next[j - 1] 的位置
        int[] next = new int[str.length];
        int i = 0, j = i + 1;

        // 初始第一位是 0，因为一个字符没有最长的公共前后缀
        next[0] = 0;
        while (j < str.length) {
            // 如果俩字符相等，则说明找到一个公共前后缀，其长度为 i + 1
            // 因为是 i 之前的字符组成的公共前后缀
            // 然后 i、j 前进
            if (str[j] == str[i]) {
                next[j] = i + 1;
                i++;
                j++;
            } else {
                // 否则，i 回溯
                while (i > 0 && str[j] != str[i]) {
                    i = next[i - 1];
                }
                // 如果回溯的位置，str[j]，str[i] 相等，则同上
                if (str[j] == str[i]) {
                    next[j] = i + 1;
                    i++;
                } else {
                    // 否则 next[j] 的值就是 0，因为 i 回到头了也和 j 不相等
                    // 即从 i 到 j，没有最长的公共前后缀
                    next[j] = 0;
                }
                j++;
            }
        }

        return next;
    }
}