使用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 的位置如下图所示这两种理解是等价的。