本文共 1392 字，大约阅读时间需要 4 分钟。

KMP的核心是next数组

next数组是依据待匹配字符串计算出来的，和待匹配字符串的长度一致。

计算过程如下:

int[] next = new int[ne.length];        next[0] = -1;         int j = 0, k = -1;        while(j < needle.length() - 1){//计算next数组            if(k == -1 || ne[k] == ne[j]){                next[++j] = ++k;            }else{                k = next[k];            }        }

计算出next数组后，当待匹配字符串哪个字符串出现失配，则向右移动(失配下标 - next[失配下标]）个位置。

​​class Solution {    public int strStr(String haystack, String needle) {        if(needle.length() > haystack.length())            return -1;        if(needle.length() == 0)            return 0;        char[] hs = haystack.toCharArray();        char[] ne = needle.toCharArray();        int[] next = new int[ne.length];        next[0] = -1;         int j = 0, k = -1;        while(j < needle.length() - 1){//计算next数组            if(k == -1 || ne[k] == ne[j]){                next[++j] = ++k;            }else{                k = next[k];            }        }        int i = 0, head;        while(i <= (haystack.length() - needle.length())){             head = i;             int m = 0;             for(m = 0; m < needle.length(); m++){                 if(ne[m] != hs[i]){                     i = head+(m-next[m]);                     break;                 }                 i++;             }            if(m == needle.length()){                return head;            }        }        return -1;    }}​​

转载地址：http://dizji.baihongyu.com/