Z 函數（擴展 KMP）

約定：字符串下標以 \(0\) 為起點。

定義

對於一個長度為 \(n\) 的字符串 \(s\)，定義函數 \(z[i]\) 表示 \(s\) 和 \(s[i,n-1]\)（即以 \(s[i]\) 開頭的後綴）的最長公共前綴（LCP）的長度，則 \(z\) 被稱為 \(s\) 的 Z 函數。特別地，\(z[0] = 0\)。

國外一般將計算該數組的算法稱為 Z Algorithm，而國內則稱其為 擴展 KMP。

這篇文章介紹在 \(O(n)\) 時間複雜度內計算 Z 函數的算法以及其各種應用。

解釋

下面若干樣例展示了對於不同字符串的 Z 函數：

\(z(\mathtt{aaaaa}) = [0, 4, 3, 2, 1]\)
\(z(\mathtt{aaabaab}) = [0, 2, 1, 0, 2, 1, 0]\)
\(z(\mathtt{abacaba}) = [0, 0, 1, 0, 3, 0, 1]\)

樸素算法

Z 函數的樸素算法複雜度為 \(O(n^2)\)：

實現

C++Python

vector<int> z_function_trivial(string s) {
  int n = (int)s.length();
  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;
}

def z_function_trivial(s):
    n = len(s)
    z = [0] * n
    for i in range(1, n):
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
    return z

線性算法

如同大多數字符串主題所介紹的算法，其關鍵在於，運用自動機的思想尋找限制條件下的狀態轉移函數，使得可以藉助之前的狀態來加速計算新的狀態。

在該算法中，我們從 \(1\) 到 \(n-1\) 順次計算 \(z[i]\) 的值（\(z[0]=0\)）。在計算 \(z[i]\) 的過程中，我們會利用已經計算好的 \(z[0],\ldots,z[i-1]\)。

對於 \(i\)，我們稱區間 \([i,i+z[i]-1]\) 是 \(i\) 的 匹配段，也可以叫 Z-box。

算法的過程中我們維護右端點最靠右的匹配段。為了方便，記作 \([l,r]\)。根據定義，\(s[l,r]\) 是 \(s\) 的前綴。在計算 \(z[i]\) 時我們保證 \(l\le i\)。初始時 \(l=r=0\)。

在計算 \(z[i]\) 的過程中：

如果 \(i\le r\)，那麼根據 \([l,r]\) 的定義有 \(s[i,r] = s[i-l,r-l]\)，因此 \(z[i]\ge \min(z[i-l],r-i+1)\)。這時：
- 若 \(z[i-l] < r-i+1\)，則 \(z[i] = z[i-l]\)。
- 否則 \(z[i-l]\ge r-i+1\)，這時我們令 \(z[i] = r-i+1\)，然後暴力枚舉下一個字符擴展 \(z[i]\) 直到不能擴展為止。
如果 \(i>r\)，那麼我們直接按照樸素算法，從 \(s[i]\) 開始比較，暴力求出 \(z[i]\)。
在求出 \(z[i]\) 後，如果 \(i+z[i]-1>r\)，我們就需要更新 \([l,r]\)，即令 \(l=i, r=i+z[i]-1\)。

可以訪問這個網站來看 Z 函數的模擬過程。

實現

C++Python

vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r and z[i - l] < r - i + 1:
            z[i] = z[i - l]
        else:
            z[i] = max(0, r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

複雜度分析

對於內層 while 循環，每次執行都會使得 \(r\) 向後移至少 \(1\) 位，而 \(r< n-1\)，所以總共只會執行 \(n\) 次。

對於外層循環，只有一遍線性遍歷。

總複雜度為 \(O(n)\)。

應用

我們現在來考慮在若干具體情況下 Z 函數的應用。

這些應用在很大程度上同前綴函數的應用類似。

匹配所有子串

為了避免混淆，我們將 \(t\) 稱作文本，將 \(p\) 稱作模式。所給出的問題是：尋找在文本 \(t\) 中模式 \(p\) 的所有出現（occurrence）。

為了解決該問題，我們構造一個新的字符串 \(s = p + \diamond + t\)，也即我們將 \(p\) 和 \(t\) 連接在一起，但是在中間放置了一個分割字符 \(\diamond\)（我們將如此選取 \(\diamond\) 使得其必定不出現在 \(p\) 和 \(t\) 中）。

首先計算 \(s\) 的 Z 函數。接下來，對於在區間 \([0,|t| - 1]\) 中的任意 \(i\)，我們考慮以 \(t[i]\) 為開頭的後綴在 \(s\) 中的 Z 函數值 \(k = z[i + |p| + 1]\)。如果 \(k = |p|\)，那麼我們知道有一個 \(p\) 的出現位於 \(t\) 的第 \(i\) 個位置，否則沒有 \(p\) 的出現位於 \(t\) 的第 \(i\) 個位置。

其時間複雜度（同時也是其空間複雜度）為 \(O(|t| + |p|)\)。

本質不同子串數

給定一個長度為 \(n\) 的字符串 \(s\)，計算 \(s\) 的本質不同子串的數目。

考慮計算增量，即在知道當前 \(s\) 的本質不同子串數的情況下，計算出在 \(s\) 末尾添加一個字符後的本質不同子串數。

令 \(k\) 為當前 \(s\) 的本質不同子串數。我們添加一個新的字符 \(c\) 至 \(s\) 的末尾。顯然，會出現一些以 \(c\) 結尾的新的子串（以 \(c\) 結尾且之前未出現過的子串）。

設串 \(t\) 是 \(s + c\) 的反串（反串指將原字符串的字符倒序排列形成的字符串）。我們的任務是計算有多少 \(t\) 的前綴未在 \(t\) 的其他地方出現。考慮計算 \(t\) 的 Z 函數並找到其最大值 \(z_{\max}\)。則 \(t\) 的長度小於等於 \(z_{\max}\) 的前綴的反串在 \(s\) 中是已經出現過的以 \(c\) 結尾的子串。

所以，將字符 \(c\) 添加至 \(s\) 後新出現的子串數目為 \(|t| - z_{\max}\)。

算法時間複雜度為 \(O(n^2)\)。

值得注意的是，我們可以用同樣的方法在 \(O(n)\) 時間內，重新計算在端點處添加一個字符或者刪除一個字符（從尾或者頭）後的本質不同子串數目。

字符串整週期

給定一個長度為 \(n\) 的字符串 \(s\)，找到其最短的整週期，即尋找一個最短的字符串 \(t\)，使得 \(s\) 可以被若干個 \(t\) 拼接而成的字符串表示。

考慮計算 \(s\) 的 Z 函數，則其整週期的長度為最小的 \(n\) 的因數 \(i\)，滿足 \(i+z[i]=n\)。

該事實的證明同應用前綴函數的證明一樣。

練習題目

本頁面主要譯自博文 Z-функция строки и её вычисление 與其英文翻譯版 Z-function and its calculation。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：LeoJacob, Marcythm, minghu6
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用