45-字符串搜索-KMP算法-节省移动的次数

题目链接

class Solution {
    public int strStr(String haystack, String needle) {
        int len = haystack.length();
        int[] next = getNext(needle);
        int j = -1; // 表示的是需要字符串搜索的下标
        for(int i = 0; i < len; i++) {
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)) {
                j = next[j];
            }
            if(haystack.charAt(i) == needle.charAt(j+1)) {
                j++;
            }
            if(j+1 == needle.length()) {
                return i-needle.length()+1;
            }
        }
        return -1;
    }
    public int[] getNext(String needle) {
        // 构建next数组
        int len = needle.length();
        int[] next = new int[len];
        int j = -1; // 使用-1表示对应下标的前缀匹配长度
        next[0] = j;
        for(int i = 1; i < len; i++) {
            // 需要j是大于-1才能进行查找前后缀匹配的长度
            while(j >= 0 && needle.charAt(i) != needle.charAt(j+1)) {
                // 找到匹配不到或者匹配到为止
                j = next[j];
            }
            // j+1是因为会为-1
            if(needle.charAt(j+1) == needle.charAt(i)) {
                j++; // 说明当前j下表2和对应的i下标值相等
            }
            next[i] = j;
        }
        return next;
    }
}