代码随想录算法训练营day09 | leetcode 28. 实现 strStr()

LeetCode 28. 实现 strStr()

牢记一点：next[i] 元素表示【0，i】子串的最长相等前后缀个数，也是模式串与主串匹配不相等时模式串的下一个比较索引

分析1.0

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

明确主串、模式串，当模式串与主串不一致时，模式串指针移动，可以移动到模式串第一个元素或非第一个元素

进而要搞懂最长相等前后缀，当指向j时，模式串[0,j]的最长相等前后缀是多少，如果是3，那next[j]=3，3是最长相等前后缀个数，而3正好是模式串下一个要比较元素的索引，而next数组从索引0开始计算，0 1 2三个索引对应最长相等前后缀，于是要比较的刚好就是第3个，很玄乎但就是这样。

可以看出模式串与前缀表对应位置的数字表示的就是：下标j之前（包括j）的字符串中，有多大长度的相同前缀后缀

j为遍历指针，只能++； i是最长相等前缀的最后一个元素的索引，可向前移动 | 比较过程可以说是模式串自己比自己

class Solution {

    public int strStr(String haystack, String needle) {

        int i = 0, j = 0;

        int[] next = getNext(needle);

        while(i < haystack.length() && j < needle.length()){

            if(haystack.charAt(i) == needle.charAt(j)){

                i++;

                j++;

            }else{

                // 比到模式串第一个还不等 那只能为0了

                if (j == 0 && next[j] == 0){

                    i++;

                    continue;

                }

                // 这是关键

                j = next[j-1];

            }

        }

        int pos = i - needle.length();

        //System.out.println(pos);

        return j == needle.length() ? pos : -1;

    }

    int[] getNext(String s){

        int len = s.length();

        int[] next = new int[len];

        // 一个元素没有前缀

        next[0] = 0;

        // i指向前缀末尾 j遍历模式串，遍历时计算next[j] 表示在模式串、主串比较过程中，如果不匹配，j应该怎么移动

        int i = 0, j = 1;

        while(j < len){

            if(s.charAt(j) == s.charAt(i)){

                // 相等 意味着最长相等前后缀又多了一个 而此时最长相等前后缀有i个 赋值后 i j都要后移一位

                next[j++] = i++ + 1; // ++i也可

            }else{

                // 不等了，应该向前移动i指针，找到可能和j指针相等的那个元素

                // 如果i移动到了第一个元素还不相等

                if (i == 0 && next[i] == 0) {

                    next[j++] = 0;

                    continue;

                }

                // 求前i-1个元素的最长相等前后缀个数，个数正好就是下一个i的索引 玄乎

                i = next[i-1];

            }

        }

        // System.out.println(Arrays.toString(next));

        return next;

    }

}

巴特西

代码随想录算法训练营day09 | leetcode 28. 实现 strStr()

LeetCode 28. 实现 strStr()

最新文章

热门文章