Z algorithm

Z algorithm 是一個用於字串處理的演算法。

輸入/輸出

• Input: 字串s (長度為n)
• Output: 陣列Z (長度為n)
  • Z[i]: 從index i 開始，與 s 的 prefix相同的最長長度。
• 時間複雜度: O(n)

使用情境

範例

• Input: "aaaa", Output: [0, 4, 3, 2, 1]

實作

• 定義Z[0] 為 0

Naive 演算法

// 複雜度: O(n^2)
void z_func(string s) {
    int n = s.size();
    vector<int> z(n);
    for(int i = 1; i < n; i++) {
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
    }
    return z;
}

優化後演算法

• index i 從小造訪到大，代表current index，用來計算Z[i]
• 維護index [l, r)，代表目前演算法找到的最右邊的prefix的範圍

以下分成幾種case來討論:

1. i >= r:
   • 代表目前位置超過紀錄的prefix範圍，須執行naive 演算法算出 z[i] 的值。
     • Note: 執行naive演算法後，r的位置可能會超過i。
2. i < r:
   • 目前index小於最右邊prefix的範圍，可以用已知的資訊幫助計算z[i]。
     • 觀察發現 s[l:r] 等於 s[0:r - l]
       • 也就代表 s[i:r] = s[i - l: r - l]
       • 因此可以從 z[i] = z[i - l] 開始計算
     • 但z[i-l]在當 i 接近字串結尾時下作為起始值可能會太大
       • 因此 z[i] 的起始值須與 r - i 取mininum。

Code

// 複雜度: O(n)
vector<int> z_function(string s) {
    int n = s.size();

    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if (i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        
        // run trival algo
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }

        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}