[数据结构与算法]kmp算法匹配字符串

搞懂kmp算法next数组的原理后，自己写了主函数匹配字符串，ac了，个人还是比较喜欢从0开始而不是从-1开始，以后就选从0开始的方法了。

https://leetcode-cn.com/problems/implement-strstr/

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        if(needle.length() == 0) return 0;
        char[] need = needle.toCharArray();
        char[] hay = haystack.toCharArray();
        getNext(next,need);
        int j = 0;
        for(int i = 0; i < haystack.length();i++) {
            //开始匹配主串，如果相等j++
            if(hay[i] == need[j]) {
                j++;
            }else {
                //不相等的话，根据next数组的值，将j回退到模式串对应位置，由于for循环会i++,然而我们要重新匹配一次这个位置，所以在这个条件下i--;
                if(j > 0) {
                    j = next[j - 1];
                    i--;
                }
            }
            if(j == needle.length()) return i - j + 1;
        }
        return -1;

    }

    public void getNext(int[] next,char[] s) {
        //初始化next数组
        int j = 0;
        next[0] = j;
        //后缀从1开始扫描整个模式串
        for(int i = 1; i < s.length;i++){
            //如果前后缀不相同，next数组就回退到上一个前后缀都相同的位置，其实就是确保接下来接住的位置的后缀正好等于主串的前缀，所以才能接上
            while(j > 0 && s[i] != s[j]){
                j = next[j - 1];
            }
            //如果相同j就前移一位，而且这个位置的next数组的值就是j
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
    }
}

next数组用了动态规划的思想，我还没有集中练习动态规划，等多练一些动态规划的题可能对这个理解就更深了。

！！！对比了一下代码随想录的主函数，我发现调换主函数的情况处理，代码上简洁一些了，贴上来码着

public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        if(needle.length() == 0) return 0;
        char[] need = needle.toCharArray();
        char[] hay = haystack.toCharArray();
        getNext(next,need);
        int j = 0;
        for(int i = 0; i < haystack.length();i++) {
            //优先处理不匹配的情况，让模式串指针j回退，如果j = 0，即还在第一位就略过，继续扫
            while(j > 0 && hay[i] != need[j]){
                j = next[j - 1];
            }
            //直到从模式串开头匹配或者字符匹配了，j++
            if(hay[i] == need[j]) j++;
            if(j == needle.length()) return i - j + 1;
        }
        return -1;

    }