被KMP算法折磨了幾天，終於搞明白lps數組，或者叫next數組計算過程中非常關鍵點的原理，這裏着重在證明為什麼這樣計算。

1 public static int[] buildLPS(String pat) {
 2     int n = pat.length();
 3     int[] lps = new int[n];
 4 
 5     int prefixLen = 0; // 當前已匹配的最長前後綴長度
 6     int i = 1;         // 正在處理 lps[i]
 7 
 8     while (i < n) {
 9         if (pat.charAt(i) == pat.charAt(prefixLen)) {
10             prefixLen++;
11             lps[i] = prefixLen;
12             i++;
13         } else if (prefixLen > 0) {
14             // 需要證明的部分
15             prefixLen = lps[prefixLen - 1];
16         } else {
17             lps[i] = 0;
18             i++;
19         }
20     }
21     return lps;
22 }

以上是計算lps數組的方法，lps數組表示了位於當前座標i時，pat[0...i]中最長相同前後綴的長度。

line 9-13 説明了當pat[i] = pat[prelen]的時候，只需要繼續沿用之前的最長前後綴長度就可以了

難點在理解line 15 為什麼回退的時候 prefixLen=lps[prefixLen-1]而不是其他的值。以下是是證明過程：

當前len = lps[i-1]，及pat[0..i-1]的最長相同前後綴長度，及pat[0...len-1] = pat[i-len..i-1]。

當pat[len] != pat[i]時，表示不能繼續沿用之前的len = lps[i-1]，

而是需要重新尋找一個t，滿足pat[0...t-1]+pat[t] = pat[i-t...i-1]+pat[i]，相當於pat[0...t-1] = pat[i-t...i-1]，根據lps定義，及我們需要找一個pat[0...i-1]的長度為t且相同的前後綴。

已知len=lps[i-1]是不滿足條件的，所以t<len。

目前

1. pat[0...len-1] = pat[i-len..i-1]

2. pat[0...t-1] = pat[i-t...i-1]

3. t<len

可知

pat[0...t-1]+pat[t..len-1] =pat[i-len..i-t-1]+pat[i-t...i-1]

由此可得 pat[i-t...i-1] （長度t) 是pat[0...len-1] = pat[0...t-1]+pat[t..len-1] 的後綴

又因為pat[0...t-1]（長度t) 是pat[0...len-1] 的前綴

所以t是pat[0...len-1]的某一個相同的前後綴的長度。

t的最大值是lps[len-1], 及pat[0..len-1]的最長相同前後綴長度。

一個比較好體現這個過程的例子：aabaabaaa

lps是 [0, 1, 0, 1, 2, 3, 4, 5, 2]

TRANSLATE with x

English

TRANSLATE with

COPY THE URL BELOW

Back

EMBED THE SNIPPET BELOW IN YOUR SITE

Enable collaborative features and customize widget: Bing Webmaster Portal

Back