Z Algorithm

Codeforces: Z Algorithm

演算法筆記: String Matching: Gusfield's Algorithm （ Z Algorithm）

定義

定義一個函數 z() ， z(i) 是指由 s[i] 開始的字串，與 s[0] 開始的字串可以匹配到多長。也就是說 s[0 ... z(i)-1] = s[i ... i+z(i)-1] 。

Ex:
  | 0 1 2 3 4 5 6 7
--+-----------------
s | a b a a b a a b
z | 8 0 1 5 0 1 2 0

z(0)：abaabaab，長度8。
z(1)：Ø，長度0。
z(2)：a，長度1。
z(3)：abaab，長度5。

實作

Z 演算法在實作上是利用已經算好的 Z[L] 來計算現在要算的 Z[i]， [L, R] 為已經算過的範圍，R = L + z[L] - 1，而根據 i 有沒有在 [L, R] 的區間內，主要可以分成以下兩種情形:

1. i 在 [L, R] 區間的外面 (i > R)，此時已經計算過的部分用不到，於是從 S[i] 跟 S[0] 開始比對，並且更新 [L, R] 區間

   

2. i 在 [L, R] 區間的裡面，其中又可以根據 z[i - L] 的值分成以下兩種：

   

   • i + z[i - L] < R + 1，代表考慮 z[i - L] 還是跨不出 [L, R] 的範圍，可以把結果拿來用 z[i] = z[i - L]

     

   • i + z[i - L] >= R + 1，代表考慮 z[i - L] 會剛好貼齊或是超出 [L, R] 的邊界，從 R + 1 開始計算，並且更新 [L, R] 區間

     

Java 程式碼如下

private void zFunction(String str) {
    int n = str.length();
    int L = 0, R = 0;
    int[] z = new int[n];
    z[0] = n;
    for (int i = 1; i < n; i++) {
        if (i > R) {
            L = R = i;
            while (R < n && str.charAt(R-L) == str.charAt(R)) {
                R++;
            }
            z[i] = R-L;
            R--;
        } else {
            int k = i - L;
            if (z[k] < R - i + 1) {
                z[i] = z[k];
            } else {
                L = i;
                while (R < n && str.charAt(R-L) == str.charAt(R)) {
                    R++;
                }
                z[i] = R-L;
                R--;
            }
        }
    }
}