KMP算法——next数组

字符串的next数组，也即前缀表。

字符串前缀：不包含最后一个字符的所有以第一个字符开头的连续子串，后缀同理。

如字符串 "abcabf" ：

"a" 的前后缀长度为0，即 next[0] = 0，

"ab"的前后缀长度为0，即 next[1] = 0，

"abc"的前后缀长度为0，即 next[2] = 0，

"abca"的前后缀长度为1，即 next[3] = 1，

"abcab"的前后缀长度为2，即 next[4] = 2，

"abcabf"的前后缀长度为0，即 next[5] = 0。

代码如下：

 1     String s = "abcabf";
 2     int next[] = new int[s.length()];
 3     for( int left = 0, right = 1;right) {
 4         while (left > 0 && s.charAt(left) != s.charAt(right)) {
 5             left = next[left - 1];      //重置left
 6         }
 7         if (s.charAt(left) == s.charAt(right))
 8             left++;
 9         next[right] = left;
10     }

如果s.charAt(left) 等于 s.charAt(right)，保存当前位置的next值，两指针都右移一位；

如果s.charAt(left) 不等于 s.charAt(right)，重置 left 指针，不能直接将其赋值为0，要取 left 指针前子串的前后缀长度。

如下所示：

此时 f != e，若 left = 0，a 还是不等于 e，但 abe == abe；

将 left = next[ left - 1 ]，left = next[4]，为2，直接从e开始与最后一个字符比较。

2022-2-12 12：00