KMP算法的实现过程

　　朴素的字符串匹配算法的时间复杂度为O(m*n)，m、n分别为主串、模式串的长度。容易理解的是，主串和模式串的指针同步进行，当遇到不匹配的字符时，主串指针将移动到当前指针下一位，因此最坏情况下m个字符都要匹配n次。而KMP算法能在O(m + n)的时间复杂度内完成查找，原理不再介绍，下面介绍实现过程。

　　（1）首先在主串与模式串前均添加任一字符，使检索时索引从1开始。

　　（2）预处理计算出next数组以免后来匹配时重复计算。next数组的作用即当出现主串、模式串不匹配的情况时，模式串指针需要从当前位置j跳转到next[j]的位置重新进行匹配。计算next数组的时间复杂度为O(n)，n为模式串长度。设i为计算next[i]的主索引，默认next[1] = 0直接跳过，令j = 0，i = 2。开始i++循环，若p[i] = p[j + 1]，则j向右一位，next[i] = j；若p[i] != p[j + 1]，此时跳转j = next[j]，直到j = 0或p[i] = p[j + 1]时停止跳转，若此时p[i] = p[j + 1]，重复上一动作，next[i] = j。

int[] next = new int[n + 1];
for(int i = 2, j = 0; i <= n; i++){
        while(j > 0 && p[i] != p[j + 1]) j = next[j];
        if(p[i] == p[j + 1) j++;
        next[i] = j;
}