模式匹配

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

这个是个模式匹配问题，我刚开始没有意识到到，用暴力法匹配所有的子串，解决了问题，虽然在短字符串的匹配中速度比kmp快，但是长字符串的效率很低。
看了解答后，才意识到这是我数据结构中学到的 KMP算法。

核心NEXT数组

next数组是求 前缀，后缀最长的公共子串长度

• 求next函数值的问题可以看成另一个模式匹配问题：整个模式串既是子串又是模式串

public int[] get_next(String needle){
    int[] next = new int[needle.length()];
    //i是后缀，j是前缀，前缀固定，后缀是相对的
    int i = 0, j = -1;

    next[0] = -1;

    while(i < needle.length()-1){
        if(j == -1 || needle.charAt(i) == needle.charAt(j)){
            i++; j++;
            //next数组优化，当字符失配时，回到相同字符无意义，应继续递归
            if(needle.charAt(i) != needle.charAt(j)) next[i] = j;
            else next[i] = next[j];
        }else
            j = next[j];//j回溯
    }

    return next;

strStr的实现

public int strStr(String haystack, String needle) {
    if(needle.length() == 0) return 0;

    int i = 0, j = 0;
    int[] next = get_next(needle);

    while(i < haystack.length() && j < needle.length()){
        if(j == -1 || haystack.charAt(i) == needle.charAt(j)) {i++; j++;}
        else j = next[j];
    }
    if(j == needle.length()) return i-j;

    return -1;
}