实现“strStr()”新增算法竞赛版本

[zerd1y]

感觉算法竞赛版本的KMP算法更加精简，更好理解
采用字符串拼接方法，只需找到pi[i] == m的位置
附上解释链接：https://oi-wiki.org/string/kmp/

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        String s = needle + "#" + haystack;
        int[] pi = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            int len = pi[i - 1];
            while (len > 0 && s.charAt(i) != s.charAt(len)) {
                len = pi[len - 1];
            }
            if (s.charAt(i) == s.charAt(len)) {
                pi[i] = len + 1;
                if (pi[i] == m) {
                    return i - m * 2;
                }
            }
        }
        return -1;
    }
}