KMP 算法的理解与应用

The reason why I encount KMP algotithm once again is leetcode 28, implement strStr.

The best practice for this problem is KMP. Needless to speak more words, KMP is very important, and when I was reading Introduction to Alogorithm, I saw it, then I went to read Algorithm 4th edition, I cannot understand it either, for some reasons, some are theirs's, some are mine.

Now, when I try to solve this leetcode problem, I think this time I grasp it well.

The following are my processing draft papers:

public class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = generateNext(needle);
        int j = 0;
        int i = 0;
        while (i < haystack.length()) {
            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 - j + 1);
            }
            i++;
        }

        return -1;
    }

    public int[] generateNext(String s) {
        int j = 0;
        int[] next = new int[s.length()];
        next[0] = j;
        int i = 1;
        while (i < s.length()) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
            next[i] = j;
            i++;
        }

        return next;
    }

    public static void main(String[] args) {
        var solu = new Solution();
        String haystack = "aabaabaafa";
        String needle = "aabaaf";
        int res = solu.strStr(haystack, needle);
        System.out.println(res);
    }
}