leetcode 题目：28. 实现 strStr()
上文 [一文说透] KMP 字符串匹配算法 中的 next 还有优化空间。
next 数组的失配状态转移图
观察上图可以发现，模式串在第 6 位失配时，需要跳转到第 1 位，但是 pattern[6] == pattern[1]，因此第 1 位肯定也会失配。
这样就做了无用功。
通过 [一文说透] KMP 字符串匹配算法 的讲解我们知道——next[j] = k 表示模式串在第 j 位和文本串失配后，模式串指针应该跳转到第 k 位。
文本串指针保持不变的情况下，如果 pattern[j] == pattern[k]，模式串在第 j 位失配，那么模式串在第 k 位也会失配。
于是我们可以改进计算 next[] 的方法，完整代码如下所示：
public static int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int k = -1;
for (int j = 1; j < pattern.length(); ++ j) {
// 循环计算
// 结果(1) 为 k = -1
// 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
k = next[k];
}
// -1 ++ 后等于 0
// 所以 next[1] 也可以合并到循环中处理
k ++;
// 如果 pattern[j] == pattern[k]
// 那么第 j 位失配的话，第 k 位也会失配
if (pattern.charAt(j) == pattern.charAt(k)) {
// 所以让 next[j] = next[k]
// 从而直接跳过第 k 位的匹配
next[j] = next[k];
} else {
next[j] = k;
}
}
return next;
}
输出为：
A B A B C A B A B D
-1 0 -1 0 2 -1 0 -1 0 4
next 数组 2.0 的失配状态转移图
