Z-AlgorithmZ 函數

01為什麼需要它

看到這些關鍵字就想到它：每個位置和字串開頭的最長共同前綴、在模式加分隔字元加文字上找 Z 值等於 m 的位置、週期與重複單元、容許少量錯誤的比對（正反各做一次）、字串旋轉。

02核心概念

Z 陣列的定義是：Z[i] 等於「整個字串 s」和「從 i 開始的後綴 s[i..]」的最長共同前綴長度。Z[0] 就是整串長度，通常不使用。每個位置都從頭逐字元比，遇到 aaaa…a 這種字串就是 O(n²)。Z 演算法維護一個視窗 [l, r]：在目前算過的位置裡，匹配區間 [i, i + Z[i] − 1] 伸得最右邊的那一段。視窗的性質是 s[l..r] 和開頭的 s[0..r−l] 一模一樣。

算 Z[i] 時分成三種情況。若 i > r，i 在視窗外，沒有資訊可借，只能從頭逐字元比，比完如果伸得比 r 遠就換成新視窗。若 i 在視窗內，因為視窗和開頭相同，s[i..r] 就是 s[i−l..r−l]，i − l 叫做 i 的鏡像位置，它的 Z 值早就算好了。鏡像值比剩餘的 r − i + 1 格小，代表鏡像那邊的匹配在視窗範圍內就斷了，i 這邊一樣會在同一處斷，直接抄 Z[i] = Z[i−l]，零次比較。鏡像值大於等於剩餘格數時，只能確定前 r − i + 1 個字元相同，視窗外的字元沒有看過，要從 r 的下一格繼續往後比，再更新視窗。

複雜度：往後比時，每次比對成功都讓 r 往右推一格，r 只增不減、最多到 n，所以成功的比較總共不超過 n 次；失敗的比較每個 i 最多一次。整體 O(n) 時間、O(n) 空間。做字串比對時，把模式、一個不會出現的分隔字元、文字接起來求 Z 陣列：分隔字元讓 Z 值不會超過 m，某個位置的值剛好是 m，就代表文字從那裡開始出現一次模式，總共 O(n + m)。和 KMP 相比，KMP 的 pi 表只存模式的 O(m)，文字可以是串流；Z 演算法要把整串接起來，但「每個位置和開頭對上幾個」的定義更直觀，也更容易組合出其他應用。

常見的坑：抄鏡像值時忘了和 r − i + 1 取最小值，會把視窗外沒看過的字元也當成相同；視窗的右端用閉區間還是半開區間要前後一致，差一就錯；忘了放分隔字元，Z 值會越過模式伸進文字，「等於 m」的判斷就不可靠；把 Z[0] 當成一般值使用。實用性質：i + Z[i] = n 的每個 i 都是字串的週期，最小的那個就是最短週期，能整除 n 時字串就是這個單元的完整重複；把字串反轉再求一次，就能拿到「從結尾往前對上幾個」，組合出容許錯誤的比對。和鄰近課程的關係：Z 陣列和 KMP 的 pi 表可以在 O(n) 內互相轉換，能解的問題幾乎一樣；下一篇 Manacher 用的是同一個想法，「在伸得最遠的區間裡借鏡像位置的答案」，只是把共同前綴換成回文半徑。

03演算法步驟

1. 1令 Z[0] = n，視窗 l = r = 0，i 從 1 掃到 n − 1。
2. 2若 i ≤ r，先令 Z[i] = min(Z[i − l], r − i + 1)，這些字元保證相同，不必比；否則 Z[i] = 0。
3. 3從目前的 Z[i] 繼續逐字元比 s[Z[i]] 和 s[i + Z[i]]，相同就加 1。鏡像值比剩餘格數小時，第一次比較就會失敗。
4. 4若 Z[i] > 0 而且 i + Z[i] − 1 > r，把視窗換成 [i, i + Z[i] − 1]。
5. 5要比對時對「模式、分隔字元、文字」求 Z，值等於 m 的位置減去 m + 1 就是文字裡的起點；要找週期時，最小的滿足 i + Z[i] = n 的 i 就是最短週期。

04互動示範

s = aabcaabcaab。字串那一列藍色是目前的 i，下面一列黃色是視窗 [l, r]。i = 1 到 4 都在視窗外，只能逐字元比：Z[1] = 1，Z[2]、Z[3] 都是 0，i = 4 一口氣對上 7 個字元，視窗變成 [4, 10]，直接伸到字串結尾。接著 i = 5、6、7 都在視窗裡，綠色的鏡像位置 1、2、3，Z 值都比剩餘格數小，直接抄過來，零次比較。i = 8 的鏡像 Z[4] = 7，比剩下的 3 格大，只能確定 3 個字元相同，而視窗已經到底，所以 Z[8] = 3，視窗換成 [8, 10]；i = 9、10 再抄一次。最後 Z = [·, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]，i = 4 和 8 都滿足 i + Z[i] = n，最短週期是 4：s 由 aabc 重複拼成，最後一塊不完整。

05程式碼

Python 放 Z 函數、用分隔字元做字串比對，以及正反各求一次 Z 陣列來找「最多錯一個字元」的位置。C++ 放 Z 函數、用最短週期找出串聯重複的單元和次數，以及判斷兩條環狀序列是否只是起點不同。兩種語言的視窗都用閉區間 [l, r]，和互動示範一致。

def z_function(s):
    """z[i]：s 和 s[i:] 的最長共同前綴長度。O(n)"""
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    l = r = 0                                   # 視窗 [l, r]：s[l..r] 和 s[0..r-l] 相同
    for i in range(1, n):
        if i <= r:
            z[i] = min(z[i - l], r - i + 1)     # 抄鏡像位置的答案，但最多只能借到視窗邊界
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                           # 視窗外的部分只能逐字元比
        if z[i] and i + z[i] - 1 > r:           # 右端更遠才換視窗
            l, r = i, i + z[i] - 1
    return z


def z_search(text, pat):
    """對 pat + 分隔字元 + text 求 Z，值等於 m 的位置就是一次出現"""
    m = len(pat)
    if m == 0:
        return []
    z = z_function(pat + "\0" + text)          # 分隔字元不在字串裡，Z 值不會超過 m
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] == m]


def almost_match(text, pat):
    """最多錯一個字元的出現位置：開頭對上 a 個、結尾對上 b 個，a + b >= m - 1 就成立"""
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    front = z_function(pat + "\0" + text)
    back = z_function(pat[::-1] + "\0" + text[::-1])   # 反轉後的前綴 = 原本的後綴
    res = []
    for i in range(n - m + 1):
        a = front[m + 1 + i]                    # text[i:] 和 pat 從頭對上幾個
        b = back[m + 1 + (n - i - m)]           # text[i:i+m] 和 pat 從尾巴對上幾個
        if a + b >= m - 1:
            res.append(i)
    return res


if __name__ == "__main__":
    print(z_function("aabcaabcaab"))            # [11, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]
    print(z_search("abracadabra", "abra"))      # [0, 7]
    print(almost_match("ACGTTACGAACGT", "ACGT"))   # [0, 5, 9]：位置 5 是 ACGA，錯一個

06練習題

• LeetCode 3029Minimum Time to Revert Word to Initial State I（找滿足 i + Z[i] = n 的最小倍數）Medium
• LeetCode 2223Sum of Scores of Built Strings（答案就是整個 Z 陣列的總和）Hard
• LeetCode 3031Minimum Time to Revert Word to Initial State II（同上，長度到 10⁶ 必須線性）Hard
• LeetCode 3036Number of Subarrays That Match a Pattern II（先轉成大小關係序列再比對）Hard
• LeetCode 3303Find the Occurrence of First Almost Equal Substring（正反兩次 Z 陣列）Hard