Chương 36 - Z Function

Z function của chuỗi s: z[i] = độ dài đoạn dài nhất bắt đầu tại s[i] đồng thời là prefix của s. z[0] được set bằng n theo quy ước. Tính được trong O(n).

Z-box invariant

Z function dùng “Z-box” [l, r) = đoạn matched gần nhất với prefix của s. Đây là chìa khoá để hiểu vì sao tính được trong O(n).

              [l ........... r)
s :  ┌───┐    ┌─────────────┐
     │ A │ ...│  B = prefix  │  ...
     └───┘    └─────────────┘
     prefix    matched với prefix
       │              │
       └──────────────┴── đoạn này = prefix của s, độ dài r - l

Khi xét z[i] với i ∈ [l, r):
  • Đã biết z[i - l] (vì s[l..r) = s[0..r-l) tương ứng).
  • Lấy lower bound: z[i] = min(r - i, z[i - l]).
  • Sau đó mở rộng bằng so sánh ký tự.

Khi i ≥ r:
  • Không có thông tin → compare từ s[0].

Update Z-box khi tìm được đoạn mới dài hơn (i + z[i] > r).

Trace với s = "aabxaabxaab":

i  l  r  z[i] tính từ
0   0  0   11     (z[0] = n)
1   0  0   ?      i ≥ r, compare từ đầu
              s[1]=a, s[0]=a → match. z[1]=1 (vì s[2]=b ≠ s[1]=a)
              Update Z-box: l=1, r=2.
2   1  2   ?      i = r, không có info → compare từ đầu.
              s[2]=b ≠ s[0]=a → z[2]=0.
3   1  2   0      Tương tự, z[3]=0.
4   1  2   ?      i ≥ r, compare: s[4..]=aabxaab, prefix=aabxaab
              Match cả 7 → z[4]=7. Update Z-box: l=4, r=11.
5   4 11   ?      i ∈ [4, 11). z[5] = min(11-5, z[5-4]) = min(6, z[1]) = min(6, 1) = 1.
              Compare thêm: s[6]=b ≠ s[1]=a → dừng. z[5]=1.
6   4 11   ?      z[6] = min(5, z[2]) = min(5, 0) = 0.
7   4 11   ?      z[7] = min(4, z[3]) = min(4, 0) = 0.
8   4 11   ?      z[8] = min(3, z[4]) = min(3, 7) = 3.
              Compare thêm: i+z[i]=11=r → có thể vượt? s[11] out of bound. z[8]=3.
9   4 11   ?      z[9] = min(2, z[5]) = min(2, 1) = 1.
10  4 11   ?      z[10] = min(1, z[6]) = min(1, 0) = 0.

Final z: [11, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]

Amortize chứng minh O(n): mỗi lần “compare extend” trong while loop làm r tăng. r đơn điệu không giảm và ≤ n → tổng số extend ≤ n. Cộng O(1) cho mỗi i không extend → tổng O(n).

Mục tiêu chương

Sau chương này, bạn sẽ:

• Z function = mảng song song KMP, dễ hình dung hơn.
• z[i] = độ dài đoạn từ s[i] khớp với prefix.
• Pattern [l, r] invariant: đoạn matched gần nhất, amortize O(n).
• Z thay KMP cho hầu hết bài; KMP nhanh hơn 1 chút với prefix function.

Khi nào dùng pattern này?

• Thay thế KMP cho bài substring matching (Z function dễ hiểu hơn).
• Bài “đoạn vừa prefix vừa suffix”, “score of built strings”.
• Pattern matching với pre-computed structure (giống KMP).

Template code

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

Bài tự luyện cuối chương

• LC 1392 - Longest Happy Prefix
• LC 1163 - Last Substring in Lexicographical Order

---

36.1 Z-function - implementation & visualization

Đề bài

Tính mảng z[] cho chuỗi s. Đây là cài đặt cốt lõi để mọi bài Z function khác dùng tới.

Ví dụ

Input:  s = "aabxaabxaab"
Output: [11, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]

Giải thích vài giá trị tiêu biểu (xem trace đầy đủ ở mục "Z-box invariant"):
  z[0] = 11   (quy ước: bằng độ dài chuỗi)
  z[4] = 7    (s[4..10] = "aabxaab" trùng prefix "aabxaab")
  z[8] = 3    (s[8..10] = "aab" trùng prefix "aab")

Ràng buộc

• 1 <= len(s) <= 10^5

Clarifying questions

• s rỗng? → Trả [].
• Tất cả ký tự khác nhau? → z[i] = 0 cho mọi i > 0.

Hướng tiếp cận

Maintain [l, r] = đoạn matched gần nhất với prefix. Tại mỗi i: - Nếu i < r: dùng giá trị z[i - l] đã biết để skip. - Mở rộng z[i] bằng cách so sánh s[z[i]] với s[i + z[i]]. - Update [l, r] nếu vùng matched mới lớn hơn.

Amortize: mỗi ký tự được “extend” tối đa 1 lần → O(n).

Code Python 3

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

Trực giác Z function với s = "aabcaabxaaaz":

i :  0  1  2  3  4  5  6  7  8  9 10 11
s :  a  a  b  c  a  a  b  x  a  a  a  z
z : 12  1  0  0  3  1  0  0  2  2  1  0

• z[1] = 1: s[1..1] = "a" là prefix length 1.
• z[4] = 3: s[4..6] = "aab" là prefix length 3.
• z[8] = 2: s[8..9] = "aa" là prefix length 2.

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(n).

Bình luận

• Pattern: Z function là building block cho mọi bài Chương 36.
• Bẫy: convention z[0] = n quan trọng cho 1 số áp dụng.

Bài tự luyện liên quan

• LC 28 - strStr() (Z version, bài 36.2).

---

36.2 Find the Index of the First Occurrence (LC 28) - Z version

Đề bài

Tìm index đầu tiên của needle trong haystack, hoặc -1. Bài này dùng Z function thay vì KMP (Chương 35.1).

Ví dụ

Input:  haystack="sadbutsad", needle="sad"
Output: 0

Ràng buộc

• 1 <= len(haystack), len(needle) <= 10^4

Clarifying questions

• needle rỗng? → Trả 0 (convention).
• haystack chứa #? → Đề LC chỉ chữ thường → an toàn.

Hướng tiếp cận

combined = pattern + '#' + text. Tính z. Tìm i đầu tiên có z[i] == len(pattern), trả i - len(pattern) - 1 (vị trí trong text).

Code Python 3

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle: return 0
        combined = needle + '#' + haystack
        z = self.z_function(combined)
        target = len(needle)
        for i, v in enumerate(z):
            if v == target:
                return i - target - 1
        return -1

    @staticmethod
    def z_function(s: str) -> list[int]:
        n = len(s)
        z = [0] * n
        z[0] = n
        l = r = 0
        for i in range(1, n):
            if i < r:
                z[i] = min(r - i, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] > r:
                l, r = i, i + z[i]
        return z

Phân tích độ phức tạp

• Thời gian: O(n + m).
• Bộ nhớ: O(n + m).

Bình luận

• # là sentinel - đảm bảo z[i] không “vượt qua” boundary giữa pattern và text.

Bài tự luyện liên quan

• LC 28 - strStr() (KMP version, bài 35.1)
• LC 1392 - Longest Happy Prefix

---

36.3 Sum of Scores of Built Strings (LC 2223) - recap

Đã giải đầy đủ ở Chương 34.6 (dùng Z function).

Insight

score(s_i) = z[n - len(s_i)] (số ký tự khớp prefix khi build dần). Cộng dồn chính là sum(z[i] for i in range(1, n)) + n (cho cả z[0] = n).

Code Python 3 (recap)

class Solution:
    def sumScores(self, s: str) -> int:
        n = len(s)
        z = [0] * n
        z[0] = n
        l = r = 0
        for i in range(1, n):
            if i < r:
                z[i] = min(r - i, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] > r:
                l, r = i, i + z[i]
        return sum(z)

Phân tích độ phức tạp

• Thời gian: O(n) (Z function). Bộ nhớ: O(n).

Bài tự luyện liên quan

• LC 1392 - Longest Happy Prefix.

---

36.4 Maximum Deletions on a String (LC 2430)

Đề bài

Cho chuỗi s. Mỗi lượt thao tác, bạn được chọn một trong hai cách:

1. Chọn chỉ số i với 1 ≤ i ≤ len(s) / 2 sao cho s[0..i-1] == s[i..2i-1] (tiền tố độ dài i trùng với đoạn ngay sau nó). Xoá tiền tố độ dài i; phần còn lại của s là s[i:].
2. Nếu không tồn tại i thoả mãn, xoá toàn bộ s (kết thúc).

Trả về số lượt thao tác lớn nhất có thể thực hiện cho đến khi s rỗng.

Ví dụ

Input:  s = "abcabcdabc"
Output: 2   (số phép xoá tối đa; mỗi phép xoá tiền tố P bằng tiền tố tiếp theo)

Ràng buộc

• 1 <= len(s) <= 4000

Clarifying questions

• s = 1 ký tự? → 1 turn (xoá luôn).
• s toàn cùng ký tự? → O(n) turn.

Hướng tiếp cận

DP từ phải sang trái. dp[i] = max turn từ s[i..].

Transition: dp[i] = max(1, max(dp[i + j] + 1 for j với s[i..i+j-1] == s[i+j..i+2j-1])).

So sánh substring nhanh bằng Z function hoặc precomputed LCP.

Code Python 3

class Solution:
    def deleteString(self, s: str) -> int:
        n = len(s)
        # lcp[i][j] = LCP của s[i:] và s[j:].
        lcp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if s[i] == s[j]:
                    lcp[i][j] = lcp[i + 1][j + 1] + 1
        dp = [1] * (n + 1)
        dp[n] = 0
        for i in range(n - 1, -1, -1):
            for j in range(1, (n - i) // 2 + 1):
                if lcp[i][i + j] >= j:
                    dp[i] = max(dp[i], dp[i + j] + 1)
        return dp[0]

Phân tích độ phức tạp

• Thời gian: O(n²). Bộ nhớ: O(n²).

Bình luận

• Bẫy: so sánh substring bằng slice → O(L) mỗi check; dùng LCP table.
• Follow-up: LC 2105 (Watering Plants II) cùng kỹ thuật.

Bài tự luyện liên quan

• LC 2223 - Sum of Scores (bài 36.3)
• LC 1316 - Distinct Echo Substrings

---

36.5 Match Substring After Replacement (LC 2301)

Đề bài

Cho s, sub, và mappings[i] = [old, new] (mỗi ký tự old có thể đổi thành new ≤ 1 lần khi match). Kiểm tra sub (sau khi áp dụng tuỳ ý mappings) có là substring của s không.

Ví dụ

Input:  s="fool3e7bar", sub="leet", mappings=[["e","3"],["t","7"],["t","8"]]
Output: True

Ràng buộc

• 1 <= len(s), len(sub) <= 5000
• 0 <= len(mappings) <= 1000

Clarifying questions

• sub > s? → Trả False.
• mappings rỗng? → Match strict; chỉ True nếu sub xuất hiện trong s.

Hướng tiếp cận

Brute force O(n · m) với check thông minh (mỗi ký tự match nếu == hoặc ∈ mapping).

Z function hoặc KMP có thể adapt - phức tạp hơn.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
        m: dict[str, set[str]] = defaultdict(set)
        for a, b in mappings:
            m[a].add(b)
        def matches(a: str, b: str) -> bool:
            return a == b or b in m[a]
        n, ns = len(s), len(sub)
        for i in range(n - ns + 1):
            if all(matches(sub[j], s[i + j]) for j in range(ns)):
                return True
        return False

Phân tích độ phức tạp

• Thời gian: O(n · m).
• Bộ nhớ: O(k) với k = số mappings.

Bình luận

• Bài này KMP/Z không trực tiếp work vì điều kiện match “đa nghĩa”.

Bài tự luyện liên quan

• LC 28 - strStr()
• LC 686 - Repeated String Match

---

36.6 Distinct Echo Substrings (LC 1316) - recap

Cùng bài 34.3, nhưng dùng Z function thay rolling hash để tránh collision.

Đề bài

Đếm số substring phân biệt có dạng a + a (chuỗi nối với chính nó).

Ví dụ

Input:  text = "aaaa"
Output: 1   (echo substring duy nhất là "aa"; "aaaa" có dạng a+a nhưng đếm theo distinct)

Ràng buộc

• 1 <= len(text) <= 2000

Clarifying questions

• s = 1 ký tự? → Trả 0 (không có echo nào).

Hướng tiếp cận

Với mỗi i, tính z trên s[i:]. Tìm các j với z[j] >= j (= echo length j tại vị trí i). Gom các echo substring distinct dùng set lưu (start_i, len).

Code Python 3

class Solution:
    def distinctEchoSubstrings(self, s: str) -> int:
        def z_function(t: str) -> list[int]:
            n = len(t)
            z = [0] * n
            z[0] = n
            l = r = 0
            for i in range(1, n):
                if i < r:
                    z[i] = min(r - i, z[i - l])
                while i + z[i] < n and t[z[i]] == t[i + z[i]]:
                    z[i] += 1
                if i + z[i] > r:
                    l, r = i, i + z[i]
            return z

        seen: set[tuple[int, int]] = set()
        n = len(s)
        for i in range(n):
            z = z_function(s[i:])
            for j in range(1, len(z)):
                if z[j] >= j:
                    seen.add((i, j))   # echo "aa" với mỗi a = s[i..i+j-1]
        # Lọc distinct theo nội dung substring.
        return len({s[i:i + 2 * j] for i, j in seen})

O(n²) worst case.

Phân tích độ phức tạp

• Thời gian: O(n²) worst.
• Bộ nhớ: O(n²).

Bài tự luyện liên quan

• LC 1044 - Longest Duplicate Substring.

Tóm tắt chương & Quyết định

Z-box visualization - aabcaabxaaaz

i:    0 1 2 3 4 5 6 7 8 9 10 11
s:    a a b c a a b x a a  a  z
Z:    – 1 0 0 3 1 0 0 2 1  1  0

Box [l, r): vùng đang khớp tiền tố hiện tại. Tại mỗi i ∈ [l, r): - Nếu i + Z[i-l] < r: copy Z[i] = Z[i-l]. - Ngược lại: brute extend từ Z[i] = r - i.

Cập nhật box khi mở rộng:

i = 4: chưa có box, brute: s[4..]=aabxaaaz vs s[0..]=aabcaab... ⇒ khớp 3 ⇒ Z[4]=3, [l,r)=[4,7)
i = 5: i-l=1, Z[1]=1, i+Z[1]=6 < 7 ⇒ Z[5] = 1 (copy)
i = 6: i-l=2, Z[2]=0, 6+0=6 < 7 ⇒ Z[6] = 0
i = 7: ngoài box, brute: Z[7]=0
i = 8: brute, khớp aaz vs aab → 2 ⇒ Z[8]=2, [l,r)=[8,10)

Maximum Deletions (LC 2430) - LCP DP, không thuần Z

• Cần lcp[i][j] = LCP của suffix s[i:] và s[j:]. Có thể compute bằng Z theo cách indirect, nhưng DP 2D là cách tự nhiên hơn.
• Bài đặt trong chương này để minh hoạ rằng LCP / Z liên quan họ hàng nhưng không luôn dùng trực tiếp Z.

Match Replacement contrast

KMP/Z giả định so sánh bằng. Nếu match relation không đối xứng (vd wildcards có ràng buộc), failure function không xài được - phải DP.

Distinct Echo recap

Bài đầy đủ ở Chương 34 (rolling hash). Recap ở đây để so sánh: Z-function có thể đếm echo s[i:i+L] == s[i+L:i+2L] bằng cách kiểm tra Z[i+L] ≥ L.

---