KMP算法

文本串：aabaabaaf

模式串：aabaaf

第一步：求前缀表（next[]）

前缀表只与模式串相关，与文本串无关。前缀表即指最长相等前后缀

(前缀不包括最后一个字符，后缀不包括第一个字符)

aabaaf

字串        最长相等前后缀

a                  0

aa                1 (前缀为a,后缀也为a)

aab              0

aaba            1

aabaa          2 (前缀为aa,后缀也为aa)

aabaaf         0

因此，aabaaf的next[]为（0，1，0，1，2，0）

第二步：字符串不匹配时，找不匹配字母的前一个字母的前缀表

如，aabaaf与文本串不匹配时，

0  1  2  3  4  5  6

a  a  b  a  a  b  a  a  f

a  a  b  a  a  f

f不匹配时，应该找f的前一个字母a的前缀表，aabaa的前缀表中值为2，所以应该直接从角标2处开始匹配（角标2为b,直接将b与模式串不匹配的地方对齐）。

0  1  2  3  4  5  6

a  a  b  a  a  b  a  a  f

            a  a  b  a  a  f

第三步：代码实现

i指向后缀的末尾，j指向前缀的末尾；

1.初始化，j=0（前缀末尾为0）

2.前后缀不相同

3.前后缀相同

4.更新next

 public static void getNext(String s){
        int j = 0;
        int[] next=new int[s.length()];
        next[0] = 0;
        for(int i = 1; i < s.length(); i++) { // 注意i从1开始，这样才能和j比较
            while (j >0 && s.charAt(i) != s.charAt(j)) {
                // 处理前后缀不相同，回溯是个连续的过程，所以是while不是if
                j = next[j-1]; // 向前回溯，回溯前一位的next中的位置
            }

            if (s.charAt(i) == s.charAt(j)){
                // 找到相同的前后缀
                j++;  //最长相等前后缀长度加1
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]，不管前后缀是否相同，都要存放
        }
    }