使用next数组加速匹配过程

如果我们在匹配之前，得到这么一个关于模式 p 的每一个位置 index 失去匹配后，模式串的匹配指针应该调整为 next[index] 的 next 数组的话，那么我们的匹配过程可以变成这样：

代码

public class StrContainsKmp { public static boolean contains(String s, String p) { int ls = s.length(), lp = p.length(), i = 0, j = 0; int[] next = getNext(p);//获取关于模式串p的next数组 while(i <= ls - lp && j < lp) { if(s.charAt(i) == p.charAt(j)) { ++i; ++j; /* 如果模式串p的第一个字符p[0]和字符串s的当前字符s[i]都不匹配， 那么说明s中从i开始不可能匹配出p来，因此换下一个开头继续尝试 */ }else if(j == 0) ++i; /* 否则j位置不是0，说明它前面有匹配成功的部分， 那么此时j应该调整为next[j]的位置 */ else j = next[j]; } return j == lp; } }

next 数组能加速匹配过程，可以从下面两个方面来理解：

• 保证 i 指针不回退，指导 j 指针的调整

在我们匹配失败的时候，它可以利用我们之前已经匹配的部分字符串（以前做过的努力），在保证 i（字符串 s 的匹配指针）不回退的情况下，指导此时指针 j（模式串的匹配指针）应该做怎样的调整。前面的图示已经向大家说明了这一点。

• 跳过了一些无需验证的可能性

还记得我们的暴力做法吗？它尝试字符串 s 中每一个可能的开头位置（即验证所有的可能性），而 next 数组指导 j 的调整，可以跳过一些根本不可能匹配出来模式串 p 的位置，如下图所示：

这两种理解是等价的。