Hàm $Z$ là một hàm rất quan trọng thường được áp dụng trong các bước tiền xử lí xâu kí tự. Một trong những ứng dụng nổi bật của hàm $Z$ là trong thuật toán tìm kiếm xâu với thời gian tuyến tính. Thuật toán tìm kiếm xâu với hàm $Z$ có lẽ là thuật toán đơn giản nhất trong số các thuật toán có cùng thời gian. Thêm nữa, thuật toán này không phụ thuộc vào bảng chữ cái $\Sigma$ như một số thuật toán khác. Mình đã implement thuật toán tìm kiếm xâu dựa trên hàm $Z$ cho bài toán tìm kiếm xâu trên spoj và đã được accept. Code được đính ở cuối bài.

Hàm $Z$

 
Nói cách khác, $Z_i(S)$ là chiều dài của tiền tố dài nhất của $S[i,i+1,n]$ khớp với một tiền tố của $S[1,2,\ldots,n]$.

Ví dụ: $S[1,2,\ldots, 11] = \mathrm{AABCAABXAAZ}$, ta có $Z_5(S) = 3$ vì tiền tố dài nhất của $S[5,\ldots, 11] = \mathrm{AABXAAZ}$ khớp với tiền tố của $S[1,2,\ldots,n]$ là $\mathrm{AAB}$ và có chiều dài bằng $3$. Tương tự, $Z_6(S) = 1$.

Trong phần này, để đơn giản, ta kí hiệu $Z[i]$ thay cho $Z_i(S)$.

Với mỗi $i > 1$ với $Z[i] > 0$, ta gọi một Z-box tại $i$ là interval (đoạn) $[i, i + Z[i]-1]$ có chiều dài $Z[i]-1$. Gọi $R[i]$ là điểm cuối lớn nhất của các Z-box bắt đầu từ $i$ hoặc trước $i$. Một cách hình thức:

$R[i] = \max_{1 < j \leq i}(j + Z[j] - 1) \qquad (1)$

Gọi $L[i]$ là điểm đầu của Z-box tương ứng kết thúc tại $R[i]$. Với ví dụ trên $Z[2] = 1, R[2] = 2, L[2] = 2$ hay $Z[6] = 1, R[6] = 7, L[6] = 5$. Dựa vào định nghĩa của $Z[i]$, ta có thể tính được bảng $Z[2,3,\ldots,n]$ trong thời gian $O(n^2)$. Tuy nhiên, chúng ta có thể tính nhanh hơn thế.

Ý tưởng của thuật toán như sau:

1. Bước đầu tiên tính $Z[2], R[2], L[2]$. Ta có thể tính $Z[2]$ bằng cách duyệt từ trái sang phải của hai xâu $S[1,\ldots,n]$ và $S[2,\ldots,n]$ để tìm ra đoạn khớp dài nhất có chiều dài $Z[2]$. Sau đó gán $L[2] = 2$ và $R[2] = 2 + Z[2] - 1 = Z[2] + 1$.
2. Tại bước thứ $i$ gọi $Z[1,2,\ldots,i-1], R[1,2,\ldots,i-1], L[1,2,\ldots,i-1]$ là các giá trị đã tính được ở các bước trước. Dựa vào các giá trị này chúng ta sẽ tính $Z[i], R[i], L[i]$. Để hiểu tại sao các giá trị này lại hữu dụng trong bước $i$, ta xét ví dụ sau: Giả sử ta muốn tính $Z[31], R[31], L[31]$, chúng ta đã biết $Z[30] = 20, R[30] = 55, L[30] = 20$. Do đó, theo định nghĩa ta có $S[20,\ldots, 55]$ khớp với $S[1,\ldots,36]$. Từ đó suy ra xâu con $S[31, \ldots, 55]$ phải khớp với xâu con $S[12,\ldots, 36]$ và như vậy, $Z[31]$ có chiều dài ít nhất là $Z[12]$. Xem hình minh họa ở dưới. Ta có hai trường hợp:
   1. $i \geq R[i-1]$, trường hợp này chúng ta chỉ việc duyệt hai xâu $S[k,\ldots,n]$ và $S[1,\ldots,n]$ như bước đầu tiên và cập nhật $R[i], L[i]$.
   2. $i < R[i-1]$, đặt:

      $\alpha = i - L[i-1]+1, \beta = R[i-1] - L[i-1] + 1 \qquad (2)$

      Do $S[L[i-1],\ldots, R[i-1]]$ khớp với $S[1,\ldots,\beta]$, suy ra $S[i,\ldots, R[i-1]]$ khớp với $S[\alpha, \ldots, \beta]$, và do đó $Z[i]$ có chiều dài ít nhất là $Z[\alpha]$.
      Nếu $i + Z[\alpha] -1 < R[i-1]$ (như hình trên cùng của hình dưới đây) thì ta có thể dễ dàng suy ra $Z[i] = Z[\alpha]$ (coi như bài tập cho bạn đọc). Nếu $i + Z[\alpha] -1 = R[i-1]$ ($i + Z[\alpha] -1$ không thể lớn hơn $R[i-1]$ theo định nghĩa của $R[i-1]$), $Z[i]$ có thể lớn hơn $Z[\alpha]$ do đó, ta có thể bắt đầu duyệt so sánh $S[R[i-1]+1, \ldots,n]$ với $S[\beta-\alpha+2, \ldots,n]$ để tìm ra $Z[i]$.

Giả mã của thuật toán như sau:

 
Code của giả mã bằng C:

#define MAXN 10000

char S[];
int Z[MAXN];
int L,R;

void compute_Z_function(int n){
Z[1] = 0;
int R = 0, L = 0;
int i = 0, j = 0, k = 0, next = 0;
for(i = 2; i <=n; i++){
next  = 0;
if(i >= R){
k = i; j = 1;
next = 1; // continue comparing characters of S
} else {
int al = i - L + 1;
int be = R - L + 1;
if(i + Z[al] <= R){
Z[i] = Z[al];
} else{ // i + Z[al] -1 = R[i-1]
k = R + 1;
j = be - al + 2;
next = 1; // Z[i] is longer than Z[al], continue comparing characters of S
}

}
if(next == 1){
while(k <= n && S[k] == S[j]){
k++; j++;
}
Z[i] = j-1;
L = i; R = L + Z[i] - 1;
}
}
}

Trong giả mã trên, bước $i$ của thuật toán chỉ phụ thuộc vào $R[i-1], L[i-1]$, chúng ta có thể giảm bộ nhớ bằng cách chỉ dùng hai biến $R,L$. Ta có thể chứng minh tính đúng đắn của thuật toán ComputeZFunction bằng phương pháp quy nạp (coi như bài tập cho bạn đọc).

Phân tích thời gian: Mỗi vòng for của thuật toán ZAlgorithm hoặc mất thời gian $O(1)$ ($\mathrm{next} = \mathrm{FALSE}$ trong câu lệnh if $\mathrm{next}$) hoặc mất thời gian tỉ lệ tuyến tính với số lượng phép so sánh bằng trong câu lệnh while ($\mathrm{next} = \mathrm{TRUE}$). Do tổng số lượng phép so sánh bằng không vượt quá chiều dài của xâu $S$, số lượng phép so sánh bằng trung bình của mỗi vòng lặp for là $1$. Do đó, tổng thời gian của thuật toán ComputeZFunction là $O(n)$.

Ứng dụng hàm $Z$ trong tìm kiếm xâu

Ta có thể áp dụng hàm $Z$ để giải bài toán tìm kiếm xâu sau trong thời gian $O(m+n)$:

Gọi $\$$ là kí tự không thuộc bảng chữ cái $\Sigma$. Giả mã của thuật toán như sau:

Do hàm ComputeZFunction có thời gian tuyến tính, ta có:

Code: Z-function, zalgorithm-accepted-code.

Tham khảo

[1] Daniel M. Gusfield, Lecture Notes on Z-algorithm, UCDavis, 2011.
[2] Codeforces forum: Z-algorithm by paladin8