代码随想录-字符串-实现strStr()--KMP

题目描述

思路:典型的数据结构中的KMP算法实现

代码与解析

假设两个字符串长度分别为m和n，暴力解则为O(m*n)

引入KMP算法降低时间复杂度，求next数组是O(m) 遍历匹配串是O(n)

KMP关键思路

①求出模式串的next数组，即最长公共前后缀的长度。前缀定义，不含最后一个字母，后缀定义不含第一个字母。

next[i] 代表第i个位置的最长公共前后缀的长度

这里定义next[0]=0,即第一个字母的最长公共前后缀长度都是0

遍历模式串

j代表模式串中i位置的最长前后缀长度为j，所以不配的时候回退为next[j-1]

private static void getNext(int[] next, String s) {
            int j = 0;
            next[0] = 0;
            for (int i = 1; i < s.length(); i++) {
                while (j > 0 && s.charAt(j) != s.charAt(i))
                    j = next[j - 1];
                if (s.charAt(j) == s.charAt(i))
                    j++;
                next[i] = j;
            }
        }

模式串与匹配串

public static int strStr(String haystack, String needle) {
            if (needle.isEmpty()) return 0;
            int[] next = new int[needle.length()];
            getNext(next, needle);
            int j = 0;
            for (int i = 0; i < haystack.length(); i++) {
                while (j > 0 && needle.charAt(j) != haystack.charAt(i))
                    j = next[j - 1];
                if (needle.charAt(j) == haystack.charAt(i))
                    j++;
                if (j == needle.length())
                    return i - needle.length() + 1;
            }
            return -1;
}

整体KMP代码

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty())
            return 0;
        // 字符串的模式匹配
        int length = needle.length();
        int[] next = new int[length];
        getNext(next, needle);
        // System.out.println(Arrays.toString(next));
        int j = 0;
        // j 来对子串操作 i来操作匹配串
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            //模式串到头了,j应该是最后一个字符之后又加一了，所以j==length，而不是length-1
            if(j == length){
                return i-length+1;
            }
        }
        return -1;
    }

    // 构建next数组，用kmp算法实现此功能
    private void getNext(int[] next, String needle) {
        int j = 0;// 最长相等前后缀长度 不算第一个和最后一个字母，所以对于第一个位置，公共长度是0
        next[0] = j;
        for (int i = 1; i < next.length; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                // 其实这里比较的是i和j都向公共前后缀子串后移动了一个之后的位置
                // 不相等，回退 j是公共长度，所以应该回退到 next[j-1] 这个之前的是可能相交的公共子串部分
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }
}