next 数组正确性分析上面我们举了一个例子说明 next 数组能够指导j指针的调整同时保证 i 指针不回退并且还能跳过那些不可能的开头位置。那么为什么呢我们这里给出一般性的说明。如图所示求解 next 数组既然 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 new int[lp]; getNextArray(p, next);//获取关于模式串p的next数组 while(i ls 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; } private static void getNextArray(String p, int[] next) { int len p.length(); next[0] -1; if(len 1) return; next[1] 0; //i: 当前要求解next[i] //cn: cn始终记录next[i - 1]的值 int i 2, cn next[i - 1]; while(i len) { if(p.charAt(i - 1) p.charAt(cn)) next[i] cn; else if(cn 0) next[i] 0; else cn next[cn]; } } }复杂度分析设字符串 s 的长度是 Np 的长度是 M我们看估计 contains 方法中 while 循环体的一共执行多少次。我们设置两个量一个是 i一个是 i−j其中 i 的范围 [0,N]i-j 的范围 [0,N]。如果代码命中第 7 行的分支那么会推高 i但是 i−j 保持不变如果代码命中第 15 行的分支那么 i 和 i−j 都会被推高如果代码命中第 21 行的分支那么 i 保持不变i−j 会被推高。且在整个 while 的执行过程中变量 i 和 i−j 不会减小那么这个 while 循环运行的结果就是把这两个变量不断推到最大值。可以知道这两个变量的最大值都是 N因此 while 循环的执行次数不会超过 2N 次因此时间复杂度 O(N)。空间复杂度 O(N)。测试程序代码import java.util.Random; public class StrContainsTest { public static void main(String[] args) { int times 100_0000, maxStrLen 1000; while(times-- 0) { Random r new Random(); int len r.nextInt(maxStrLen) 2; String s getRandomStr(r, len); String p; if(r.nextInt(2) 0) p s.substring(r.nextInt(len)); else p getRandomStr(r, r.nextInt(len) 1); boolean ans1 StrContains.contains(s, p); boolean ans2 StrContainsKmp.contains(s, p); if(ans1 ^ ans2) { System.out.println(Oops!, wrong answer, ans1 ans1 , ans2 ans2); System.out.println(s: s); System.out.println(p: p); return; } System.out.println(Testcase: times done!); } System.out.println(Test done successfully!); } private static String getRandomStr(Random r, int len) { StringBuilder bd new StringBuilder(); while(len-- 0) bd.append((char)(a r.nextInt(26))); return bd.toString(); } }