Z-function

Z-function (hàm Z) của xâu $s$ độ dài $n$ là mảng $z[0..n-1]$, trong đó $z[i]$ là độ dài tiền tố chung dài nhất của $s$ và hậu tố $s[i..]$. Chỉ một mảng này đủ để tìm mọi vị trí xuất hiện của một mẫu, tìm chu kỳ của xâu, đếm biên (border), so sánh một đoạn với tiền tố... Tính ngây thơ (so từng ký tự tại mỗi $i$) mất $O(n^2)$ trên xâu như aaaa...a; thuật toán Z dùng lại thông tin cũ qua một "hộp Z" (Z-box) và chạy trong $O(n)$.

Ý tưởng / Trực giác

Định nghĩa

$$z[i]=max\{k\ge 0:s[0..k-1]=s[i..i+k-1]\},1\le i<n.$$

$z[0]$ không có ý nghĩa tự nhiên (cả xâu khớp với chính nó); trang này quy ước $z[0]=n$, nhiều đề quy ước $z[0]=0$. Ví dụ:

 i :  0  1  2  3  4  5  6  7
 s :  a  b  a  c  a  b  a  b
 z :  8  0  1  0  3  0  2  0

$z[4]=3$ vì aba (bắt đầu tại $4$) khớp tiền tố aba, còn ký tự tiếp theo b khác c.

Hộp Z: dùng lại đoạn đã khớp

Khi duyệt $i$ từ trái sang, ta giữ một đoạn $[l,r)$ gọi là hộp Z: đoạn có $r$ lớn nhất đã tìm được mà $s[l..r-1]=s[0..r-l-1]$ (tức $l+z[l]=r$). Hộp Z là "bản sao" của một tiền tố.

Xét $i$ mới:

• Trường hợp $i\ge r$: $i$ nằm ngoài mọi đoạn đã biết, không có gì để dùng lại. So từng ký tự $s[0],s[1],\dots$ với $s[i],s[i+1],\dots$ như cách ngây thơ.
• Trường hợp $i<r$: $i$ nằm trong hộp. Vì $s[l..r-1]$ giống hệt $s[0..r-l-1]$, đoạn bắt đầu tại $i$ trong hộp giống đoạn bắt đầu tại $k=i-l$ trong tiền tố, ít nhất tới biên $r$. Mà $z[k]$ đã tính rồi, nên:

$$z[i]\ge min(z[k],r-i).$$

        0     k                         l     i           r
  s :  [=====|=====……]                 [=====|=====……]    |
        \___________/                   \___________/
         tiền tố s[0..r-l-1]   ==        hộp Z s[l..r-1]

Có hai khả năng:

• $z[k]<r-i$: đoạn khớp tại $k$ kết thúc trước khi chạm biên. Ký tự làm nó dừng, $s[k+z[k]]\ne s[z[k]]$, cũng có bản sao nằm trong hộp: $s[i+z[k]]=s[k+z[k]]$. Vậy $z[i]=z[k]$ chính xác; về mặt lý thuyết không cần so sánh ký tự nào (code bên dưới vẫn thử một phép so tại vị trí $i+z[k]$, thất bại ngay rồi dừng, và đó chính là phép thất bại duy nhất của $i$ trong lập luận đếm ở mục sau).
• $z[k]\ge r-i$: ta chỉ biết chắc $z[i]\ge r-i$ (khớp tới biên). Từ $r$ trở đi là vùng chưa ai so, nên phải so tiếp từng ký tự bắt đầu tại vị trí $r$.

Cuối mỗi bước, nếu $i+z[i]>r$ thì hộp mới là $[i,i+z[i])$.

Vì sao là $O(n)$: $r$ chỉ tăng

Đếm các phép so sánh trong vòng while:

• Mỗi phép so sánh thành công xảy ra ở vị trí $i+z[i]\ge r$ (trường hợp $i\ge r$ thì bắt đầu từ $i\ge r$; trường hợp chạm biên thì bắt đầu đúng từ $r$). Sau bước đó, $r$ được cập nhật thành $i+z[i]$, nên mỗi lần khớp đẩy $r$ lên ít nhất $1$. Vì $r\le n$ và không bao giờ giảm, tổng số lần khớp $\le n$.
• Mỗi $i$ có nhiều nhất một phép so sánh thất bại (vòng while dừng ngay khi gặp nó).

Tổng cộng không quá $2n$ phép so sánh ký tự. Đây là cùng lập luận khấu hao với Manacher: biên phải của vùng đã biết chỉ tiến, không lùi.

Ví dụ chạy tay

$s=$ abacabab, $n=8$. Ban đầu $l=r=0$.

 i :  0  1  2  3  4  5  6  7
 s :  a  b  a  c  a  b  a  b

$i=1$ ($i\ge r$): so $s[0]$=a với $s[1]$=b: khác. $z[1]=0$. Hộp giữ nguyên.

$i=2$ ($i\ge r$): a=a khớp, rồi $s[1]$=b với $s[3]$=c: khác. $z[2]=1$, hộp $[2,3)$.

$i=3$ ($i\ge r=3$): a với c: khác. $z[3]=0$.

$i=4$ ($i\ge r$): a=a, b=b, a=a, rồi $s[3]$=c với $s[7]$=b: khác. $z[4]=3$, hộp mới $[4,7)$.

 i :  0  1  2  3  4  5  6  7
 s :  a  b  a  c  a  b  a  b
      [-----]     [-----]
      s[0..2]     hộp Z s[4..6] = [4, 7): l=4, r=7

$i=5$ ($i<r$): $k=5-4=1$, $z[1]=0$, $r-i=2$. Vì $z[k]=0<2$ nên $z[5]=0$ chính xác (vòng while chỉ làm một phép so sánh thất bại).

$i=6$ ($i<r$): $k=2$, $z[2]=1$, $r-i=1$. Lúc này $z[k]\ge r-i$: đoạn khớp chạm biên, chỉ biết $z[6]\ge 1$.

 i :  0  1  2  3  4  5  6  7
 s :  a  b  a  c  a  b  a  b
            ^           ^  |
            k=2         i  r=7   <- biết chắc s[6]=s[0], từ r trở đi phải so

So tiếp từ vị trí $r=7$: $s[1]$=b với $s[7]$=b: khớp, $z[6]=2$. Hết xâu. Hộp mới $[6,8)$, $r$ tiến từ $7$ lên $8$.

$i=7$ ($i<r$): $k=1$, $z[1]=0<r-i=1$ nên $z[7]=0$.

Kết quả $z=[8,0,1,0,3,0,2,0]$. Tổng cộng có $5$ phép so sánh thành công và $6$ phép thất bại, dưới $2n=16$.

Cài đặt

C++

#include <bits/stdc++.h>
using namespace std;

// z[i] = length of the longest common prefix of s and s[i..]; z[0] = n by convention
vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    if (n == 0) return z;
    z[0] = n;
    int l = 0, r = 0;                 // Z-box [l, r): s[l..r-1] == s[0..r-l-1]
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);   // reuse the mirrored value
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;  // extend past r
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

int main() {
    string s;
    cin >> s;
    vector<int> z = z_function(s);
    for (int x : z) cout << x << ' ';
    cout << '\n';
}

Hàm chỉ dùng phép == trên phần tử nên đổi string thành vector<int> là chạy được với dãy số.

Python

def z_function(s):
    n = len(s)
    z = [0] * n
    if n == 0:
        return z
    z[0] = n
    l = r = 0  # Z-box [l, r)
    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


print(z_function("abacabab"))  # [8, 0, 1, 0, 3, 0, 2, 0]

Bản Python dùng được, nhưng vòng lặp thuần Python chậm hơn C++ nhiều lần; bài có $n={10}^6$ và giới hạn thời gian chặt thì nên dùng C++.

Ứng dụng

Tìm mẫu: ghép $p+\#+t$

Để tìm mọi vị trí $p$ (độ dài $m$) xuất hiện trong $t$, tính Z của xâu $S=p+\#+t$, với # là ký tự không có trong $p$ và $t$. Vị trí $i$ trong $S$ (với $i>m$) ứng với vị trí $i-m-1$ trong $t$, và $p$ xuất hiện tại đó khi và chỉ khi $z[i]\ge m$ (thực ra $=m$).

 p = aba,  t = abacababa
 i : 0 1 2 3 4 5 6 7 8 9 10 11 12
 S : a b a # a b a c a b a  b  a
 z : - 0 1 0 3 0 1 0 3 0 3  0  1
             ^       ^   ^
     z >= 3 tại i = 4, 8, 10  ->  t chứa p tại 0, 4, 6

Vì sao cần ký tự phân cách:

• Chặn $z$ không vượt $m$. Mọi đoạn khớp bắt đầu trong $t$ phải dừng trước # của tiền tố, nên $z[i]\le m$ và $z[i]$ đúng bằng độ dài tiền tố dài nhất của $p$ bắt đầu tại $t[i-m-1]$. Không có # thì $z[i]$ có thể lớn hơn $m$, mọi chỗ dùng giá trị này (không chỉ phép so $\ge m$) phải tự cắt min(z[i], m). Đây là lợi ích chính: $z[i]$ dùng được trực tiếp làm lcp với $p$ (cho lcp/lcs, cho so sánh thứ tự).
• Đoạn vắt qua ranh giới chỉ gây nhầm khi duyệt cả những $i$ nằm trong $p$. Nếu chỉ xét các vị trí thuộc $t$ (như vòng lặp dưới đây), thì kể cả khi không có #, điều kiện $z[i]\ge m$ vẫn cho đúng các vị trí khớp, vì đoạn bắt đầu trong $t$ chỉ đọc tiếp trong $t$. Nhầm lẫn chỉ xảy ra khi duyệt $i$ từ $1$: với $p$ = aa, $t$ = ab, xâu ghép không phân cách aaab có $z[1]=2\ge m$ nhưng $i=1$ nằm trong $p$. Có # thì mọi $i$ trong $p$ đều có $z[i]<m$, nên duyệt từ $1$ cũng an toàn.

// 0-indexed starting positions of p in t
vector<int> find_occurrences(const string& p, const string& t) {
    string s = p + '#' + t;           // '#' must not appear in p or t
    vector<int> z = z_function(s);
    int m = p.size();
    vector<int> pos;
    for (int i = m + 1; i < (int)s.size(); i++)
        if (z[i] >= m) pos.push_back(i - m - 1);
    return pos;
}

Thời gian $O(n+m)$, bộ nhớ $O(n+m)$ cho xâu ghép và mảng $z$.

Chu kỳ và biên của xâu

$p$ ($1\le p\le n$) là chu kỳ của $s$ nếu $s[i]=s[i+p]$ với mọi $i$ hợp lệ. Điều này đúng khi và chỉ khi hậu tố $s[p..]$ trùng tiền tố cùng độ dài, tức

$$p+z[p]=n(\text{hoặc }p=n).$$

Tương tự, tiền tố độ dài $\ell$ là biên (vừa là tiền tố vừa là hậu tố) khi và chỉ khi $z[n-\ell ]=\ell$. Chu kỳ $p$ và biên $n-p$ luôn đi thành cặp.

// all periods of s in increasing order
vector<int> all_periods(const string& s) {
    int n = s.size();
    vector<int> z = z_function(s);
    vector<int> res;
    for (int p = 1; p < n; p++)
        if (p + z[p] == n) res.push_back(p);
    res.push_back(n);
    return res;
}

Ví dụ $s$ = abaababaab ($n=10$) có các chu kỳ $5,8,10$. Chú ý: chu kỳ nhỏ nhất $p_0$ không nhất thiết chia hết $n$. Xâu $s$ viết được thành $w^k$ ($k\ge 2$) khi và chỉ khi $p_0<n$ và $p_0\mid n$; kiểm tra $p_0\mid n$ là đủ vì nếu $s$ có một chu kỳ $d\mid n$, $d<n$ thì theo định lý Fine–Wilf ($p_0+d\le n$), $gcd(p_0,d)$ cũng là chu kỳ, suy ra $p_0\mid d\mid n$.

Đếm số xâu con phân biệt trong $O(n^2)$

Thêm lần lượt từng ký tự $c$ vào cuối xâu hiện tại $s$. Các xâu con mới xuất hiện đều là hậu tố của $s+c$. Đảo ngược $t=\text{rev}(s+c)$ thì các hậu tố đó thành tiền tố của $t$. Một tiền tố của $t$ đã có từ trước khi và chỉ khi nó xuất hiện ở vị trí $i\ge 1$ nào đó, tức độ dài $\le z_{max}={max}_{i\ge 1}{z}_t[i]$. Vậy số xâu con mới là $|t|-z_{max}$.

long long count_distinct_substrings(const string& s) {
    long long total = 0;
    string cur;
    for (char c : s) {
        cur += c;
        string t(cur.rbegin(), cur.rend());   // new substrings = prefixes of t
        vector<int> z = z_function(t);
        int zmax = 0;
        for (int i = 1; i < (int)t.size(); i++) zmax = max(zmax, z[i]);
        total += (int)t.size() - zmax;
    }
    return total;
}

Ví dụ abab cho $1+2+2+2=7$: thêm a được a; thêm b được b, ab; thêm a được ba, aba (còn a đã có, $z_{max}=1$); thêm b được bab, abab (còn b, ab đã có, $z_{max}=2$). Thời gian $O(n^2)$, đủ cho $n$ vài nghìn. Với $n$ lớn hơn, dùng mảng hậu tố hoặc suffix automaton. Cùng lập luận (đổi vai trò tiền tố/hậu tố) cho số xâu con phân biệt thay đổi thế nào khi thêm ký tự vào đầu, hoặc xóa một ký tự ở đầu hay cuối, mỗi thao tác $O(n)$.

So sánh một đoạn với tiền tố

$z[i]$ chính là $\text{lcp}(s[i..],s)$, nên với mọi $i$ ta trả lời trong $O(1)$:

• Đoạn $s[i..i+len-1]$ bằng tiền tố độ dài $len$ khi và chỉ khi $z[i]\ge len$.
• Nếu không bằng, thứ tự từ điển của hai đoạn do ký tự đầu tiên khác nhau quyết định: so $s[i+z[i]]$ với $s[z[i]]$.

Muốn so một đoạn của $t$ với tiền tố của $p$ thì dùng xâu ghép $p+\#+t$ như trên. Muốn so hai đoạn bất kỳ (không phải tiền tố) thì Z không đủ; cần hash (tìm lcp bằng chặt nhị phân) hoặc mảng hậu tố + LCP.

Một mẹo hay dùng: tiền tố đối xứng. Tiền tố độ dài $L$ của $s$ là palindrome khi và chỉ khi nó trùng hậu tố độ dài $L$ của $\text{rev}(s)$. Tính Z của $s+\#+\text{rev}(s)$; tiền tố độ dài $L$ đối xứng khi và chỉ khi giá trị Z tại vị trí $n+1+(n-L)$ đạt $\ge L$.

Chuyển đổi giữa Z-function và hàm tiền tố

Hàm tiền tố $\pi [i]$ là độ dài biên thực sự dài nhất của $s[0..i]$. Hai mảng mang cùng một lượng thông tin: cả hai đều mô tả tập các cặp (vị trí, độ dài) mà tiền tố xuất hiện, Z ghi theo điểm bắt đầu, $\pi$ ghi theo điểm kết thúc.

Z sang $\pi$. Tiền tố độ dài $j+1$ xuất hiện kết thúc tại $i+j$ với mọi $j<z[i]$. Duyệt $i$ tăng dần; với mỗi $i$ đi $j$ từ $z[i]-1$ xuống $0$ và gán $\pi [i+j]=j+1$ nếu ô đó chưa có giá trị. Khi gặp ô đã có giá trị thì dừng: ô đó được đặt bởi một điểm bắt đầu sớm hơn (cho biên dài hơn), và các ô bên trái nó cũng vậy. Mỗi ô được gán đúng một lần nên tổng $O(n)$.

vector<int> z_to_pi(const vector<int>& z) {
    int n = z.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++)
        for (int j = z[i] - 1; j >= 0; j--) {
            if (pi[i + j] > 0) break;     // already set by an earlier start (longer border)
            pi[i + j] = j + 1;
        }
    return pi;
}

$\pi$ sang Z. Cách gọn nhất: dựng lại một dãy có đúng hàm tiền tố đó, rồi chạy Z trên dãy. Đặt $t[i]=t[\pi [i]-1]$ nếu $\pi [i]>0$, ngược lại cho $t[i]$ một ký hiệu mới chưa dùng (lấy luôn $t[i]=i$). Với $\pi$ hợp lệ, dãy $t$ có hàm tiền tố bằng $\pi$, và vì hai mảng cùng thông tin nên Z của $t$ chính là Z cần tìm.

vector<int> pi_to_z(const vector<int>& pi) {
    int n = pi.size();
    vector<int> t(n);                  // a sequence with the same prefix function
    for (int i = 0; i < n; i++)
        t[i] = (pi[i] > 0) ? t[pi[i] - 1] : i;   // fresh symbol when there is no border
    vector<int> z(n, 0);
    if (n == 0) return z;
    z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && t[z[i]] == t[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

Cả hai hàm đã được kiểm tra đối chiếu với cách tính trực tiếp trên hàng chục nghìn xâu ngẫu nhiên.

Khi nào chọn Z, KMP hay hash

Z và hàm tiền tố tất định (không có rủi ro va chạm như hash), nên khi bài chỉ cần so với tiền tố thì chúng an toàn hơn.

Độ phức tạp

⚠️ Lỗi thường gặp

• Quên min(r - i, ...). Viết z[i] = z[i - l] khi $i<r$ là sai: giá trị ở tiền tố có thể "lan" ra ngoài hộp, nơi hai bản sao không còn giống nhau. Với $s$ = aaaab: tại $i=2$, hộp là $[1,4)$, $z[1]=3$ nhưng đáp án đúng $z[2]=2$. Triệu chứng: kết quả lớn hơn thực tế, thường chỉ lộ ra trên xâu có nhiều ký tự lặp.
• Lẫn hộp nửa mở $[l,r)$ với đoạn đóng $[l,r]$. Nhiều tài liệu dùng $r$ là vị trí cuối (đóng), khi đó công thức thành min(r - i + 1, z[i - l]) và điều kiện là i <= r. Trộn hai quy ước gây lệch một. Chọn một quy ước và giữ nguyên trong cả hàm.
• Quy ước $z[0]$. Code ở đây đặt $z[0]=n$; nhiều đề (và nhiều thư viện) đặt $z[0]=0$. Nếu lấy $max$ trên cả mảng mà quên bỏ $i=0$ thì luôn nhận được $n$; nếu đề yêu cầu in $z[0]=0$ mà in $n$ thì sai ngay test đầu.
• Ký tự phân cách có mặt trong dữ liệu. Đề cho xâu gồm cả ký tự đặc biệt mà vẫn dùng # thì đoạn khớp có thể đi xuyên qua ranh giới. Chọn ký tự chắc chắn không xuất hiện (ví dụ '\0' hay '$' khi đề chỉ có chữ cái), hoặc chuyển sang vector<int> và dùng phân cách $-1$.
• Tưởng $O(n)$ nhưng thực ra $O(n^2)$. Chỉ đúng tuyến tính khi dùng lại giá trị từ hộp Z. Nếu quên cập nhật hộp (if (i + z[i] > r) { l = i; r = i + z[i]; }) hoặc bỏ nhánh dùng lại z[i - l] thì vòng while so lại những ký tự đã so, và xâu aaa...a với $n={10}^6$ sẽ quá thời gian. Ngược lại, đếm xâu con phân biệt bằng Z vốn là $O(n^2)$; đừng dùng nó cho $n={10}^5$.
• Quên đảo xâu khi đếm xâu con phân biệt. Xâu con mới khi thêm ký tự vào cuối là hậu tố, còn Z nói về tiền tố. Tính Z trên $s+c$ thay vì $\text{rev}(s+c)$ cho số đếm sai.
• Nhầm "có chu kỳ" với "là lũy thừa của một xâu". Mọi xâu đều có chu kỳ nhỏ nhất $p_0$, nhưng chỉ viết được thành $w^k$ ($k\ge 2$) khi $p_0\mid n$ và $p_0<n$. Với abaab, $p_0=3$ không chia hết $5$ nên xâu không phải lũy thừa.
• Ghép xâu lặp lại cho nhiều mẫu. Với $n,m$ tới ${10}^6$, xâu ghép và mảng int tổng cộng khoảng $10$ MB, ổn. Nhưng ghép lại xâu trong vòng lặp nhiều truy vấn (mỗi mẫu một lần ghép với cả $t$) sẽ tốn $O(k·n)$ thời gian; nhiều mẫu thì cân nhắc Aho-Corasick, hash hoặc mảng hậu tố.

Biến thể / Mở rộng

• Lcp của mỗi hậu tố của $t$ với $p$. Từ $p+\#+t$ ta có luôn mảng $\text{lcp}(t[j..],p)$ cho mọi $j$, không chỉ các vị trí khớp trọn. Đảo cả hai xâu cho hậu tố chung dài nhất kết thúc tại mỗi vị trí. Ghép hai mảng này giải được bài "tìm mẫu cho phép sai đúng một ký tự": $p$ khớp tại $j$ với tối đa một chỗ sai khi $\text{lcp}+\text{lcs}\ge m-1$.
• Đếm số lần xuất hiện của mọi tiền tố. Tiền tố độ dài $\ell$ xuất hiện tại $i$ khi $z[i]\ge \ell$. Đếm cnt[z[i]]++ rồi cộng dồn từ lớn xuống nhỏ để có số vị trí $i$ với $z[i]\ge \ell$ cho mọi $\ell$, tổng $O(n)$.
• Chu kỳ vòng / xoay xâu. $t$ là một phép xoay của $s$ (cùng độ dài) khi và chỉ khi $t$ xuất hiện trong $s+s$; dùng tìm mẫu với $t+\#+s+s$.
• Dãy số thay cho xâu. Z chỉ cần phép so sánh bằng, nên áp dụng cho dãy số, hoặc cho dãy hiệu $a_{i+1}-a_i$ để tìm đoạn "cùng hình dạng" bất kể tịnh tiến.
• Thuật toán Main-Lorentz. Tìm mọi xâu con dạng $XX$ (lặp liên tiếp) theo dạng nén (từng nhóm) trong $O(n\log n)$ bằng chia để trị, mỗi tầng dùng Z trên phần trái đảo ngược và phần phải. Số lần lặp dạng $XX$ có thể tới $\Theta (n^2)$ (ví dụ aaa...a), nên không thể liệt kê từng lần một trong $O(n\log n)$; thuật toán xuất mỗi nhóm lần lặp cùng tâm và cùng độ dài dưới dạng một khoảng vị trí, đủ để đếm tổng số lần lặp hoặc tìm lần lặp dài nhất.
• Liên hệ. KMP cho cùng thông tin theo điểm kết thúc và làm được trực tuyến; hash xâu linh hoạt hơn với đoạn bất kỳ; mảng hậu tố giải các bài lcp tổng quát; Manacher dùng đúng ý tưởng "hộp + đối xứng + biên phải chỉ tiến" cho palindrome.

Bài tập luyện

Luyện kỹ thuật

• Khớp Xâu (strmatch) (Trung cấp) đếm số lần mẫu xuất hiện với $n,m\le {10}^6$: bài nhập môn cho kỹ thuật ghép $p+\#+t$ và đếm $z[i]\ge m$.
• Tìm Chu Kỳ (periods) (Nâng cao) in mọi độ dài chu kỳ: áp dụng trực tiếp điều kiện $p+z[p]=n$.
• Tiền tố trùng Hậu tố (borderocc) (Kỳ cựu) tìm mọi biên (điều kiện $z[n-\ell ]=\ell$) rồi đếm số lần mỗi tiền tố đó xuất hiện bằng mảng đếm cnt[z[i]] cộng dồn ngược.
• Hàm Xâu (strfuncs) (Kỳ cựu) in cả Z-function và hàm tiền tố với $n\le {10}^6$; chú ý quy ước $z(1)=0$ của đề, và có thể lấy $\pi$ từ $z$ bằng phép chuyển đổi ở trên.
• Bậc đối xứng (paldeg) (Kỳ cựu) cần biết mọi tiền tố nào là palindrome: dùng Z trên $s+\#+\text{rev}(s)$ (hoặc hash), sau đó bậc của tiền tố độ dài $L$ suy ra từ bậc của tiền tố độ dài $\lfloor L/2\rfloor$.

Đề VOI

Trong các đề VOI hiện có trên hệ thống, chưa có bài nào mà lời giải chính thức dùng Z-function. Bài dưới đây chỉ dùng được Z cho một subtask, như một cách giải thay thế:

• Virus (voi17_virus) (Nâng cao) VOI 2017, chỉ subtask $k=0$: đoạn cần tìm là xâu dạng $XX$. Gợi ý: cố định vị trí bắt đầu $p$ và tính Z của hậu tố $T[p..]$; mảng này cho biết nửa sau của một đoạn có lặp lại nửa đầu hay không với mọi độ dài cùng lúc, cho $O(m^2)$ tổng cộng. Lời giải chính thức cho mọi $k$ dùng cửa sổ trượt trên mảng sai khác, không dùng Z.