KMP（Knuth-Morris-Pratt ）算法-模式串lps（Longest Prefix Suffix）最长雷同前后缀长度数组算法证明
被KMP算法折磨了几天，终于搞明白lps数组，大概叫next数组盘算过程中非常关键点的原理，这里偏重在证明为什么如许盘算。1 public static int[] buildLPS(String pat) {
2 int n = pat.length();
3 int[] lps = new int;
4
5 int prefixLen = 0; // 当前已匹配的最长前后缀长度
6 int i = 1; // 正在处理 lps
7
8 while (i < n) {
9 if (pat.charAt(i) == pat.charAt(prefixLen)) {
10 prefixLen++;
11 lps = prefixLen;
12 i++;
13 } else if (prefixLen > 0) {
14 // 需要证明的部分
15 prefixLen = lps;
16 } else {
17 lps = 0;
18 i++;
19 }
20 }
21 return lps;
22 }
以上是盘算lps数组的方法，lps数组表现了位于当前坐标i时，pat中最长雷同前后缀的长度。
line 9-13 阐明白当pat = pat的时间，只须要继承相沿之前的最长前后缀长度就可以了
难点在明白line 15 为什么回退的时间 prefixLen=lps而不是其他的值。以下是是证明过程：
当前len = lps，及pat的最长雷同前后缀长度，及pat = pat。
当pat != pat时，表现不能继承相沿之前的len = lps，
而是须要重新探求一个t，满足pat+pat = pat+pat，相当于pat = pat，根据lps界说，及我们须要找一个pat的长度为t且雷同的前后缀。
已知len=lps是不满足条件的，以是t
页:
[1]