Mảng Z đo độ giống tiền tố
Với xâu s, z[i] là độ dài lớn nhất sao cho s[0:z[i]) bằng s[i:i+z[i]). Nói cách khác, nó hỏi hậu tố bắt đầu tại i giống phần đầu xâu bao xa. Bài này dùng quy ước z[0]=0; một số tài liệu đặt z[0]=n, nên cần chốt trước khi so kết quả.
Z-function chạy tuyến tính nhờ giữ cửa sổ [l,r) khớp tiền tố có biên phải xa nhất. Biên phải là nửa mở: ký tự r chưa được biết là khớp.
Từ phép so ngây thơ đến cửa sổ Z
Cách đơn giản tại mỗi i bắt đầu từ 0 rồi so s[z] với s[i+z]. Trên xâu toàn chữ a, tổng số phép so có thể là 1+2+...+(n-1), tức O(n²). Thuật toán tuyến tính tái dùng kết quả đã biết trong cửa sổ xa nhất.
Nếu i>=r, chưa có thông tin dùng lại; bắt đầu z[i]=0 và mở rộng. Nếu i<r, đoạn từ i tới r đã giống một đoạn đầu xâu. Vị trí tương ứng trong tiền tố là i-l, nên đặt ban đầu z[i]=min(r-i,z[i-l]). Giá trị bị chặn bởi r-i vì phần ngoài cửa sổ chưa được chứng minh. Sau đó tiếp tục so ký tự từ biên hiện tại.
Khi i+z[i]>r, cập nhật l=i, r=i+z[i]. Mỗi phép so thành công ngoài cửa sổ làm r tăng; r không giảm trong toàn vòng lặp. Vì vậy tổng số lần mở rộng ngoài vùng đã biết không vượt n, đem lại O(n).
Với aaaaa, kết quả theo quy ước bài là 0,4,3,2,1. Tại i=1, thuật toán mở cửa sổ tới cuối. Các vị trí sau nằm trong cửa sổ và nhận ngay giới hạn tương ứng. Đây là ví dụ tốt để phát hiện nhầm giữa biên phải đóng và nửa mở.
Tìm mẫu bằng một xâu ghép
Muốn tìm pattern trong text, dựng pattern + separator + text. Separator phải không xuất hiện trong hai xâu. Ở bản mẫu, đầu vào là dòng văn bản thông thường, còn cả C++ lẫn Python dùng ký tự \0 làm ký tự ngăn cách nội bộ (hình vẽ dùng # cho dễ nhìn). Với mỗi vị trí thuộc phần text, nếu Z ít nhất bằng độ dài mẫu thì mẫu xuất hiện tại vị trí đã trừ phần mẫu và separator.
Ví dụ ghép aba\0ababa. Hai vị trí trong phần văn bản có Z ít nhất 3, tương ứng đáp án 0 và 2. Các lần xuất hiện chồng nhau được giữ tự nhiên vì Z được tính độc lập ở mọi điểm bắt đầu. Mẫu rỗng được xử lý riêng và trả mọi ranh giới 0..n; không ghép separator rồi suy diễn trường hợp này.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> z_function(const string& s){int n=s.size(),l=0,r=0;vector<int> z(n);for(int i=1;i<n;++i){if(i<r)z[i]=min(r-i,z[i-l]);while(i+z[i]<n&&s[z[i]]==s[i+z[i]])++z[i];if(i+z[i]>r){l=i;r=i+z[i];}}return z;}
vector<int> find_all(const string& t,const string& p){if(p.empty()){vector<int>a(t.size()+1);for(int i=0;i<=(int)t.size();++i)a[i]=i;return a;}string s=p+char(0)+t;auto z=z_function(s);vector<int>a;for(int i=p.size()+1;i<(int)s.size();++i)if(z[i]>=(int)p.size())a.push_back(i-p.size()-1);return a;}
int main(){string t="ababa",p="aba",x;if(getline(cin,x)){t=x;getline(cin,p);}auto a=find_all(t,p);cout<<a.size()<<'\n';for(int x:a)cout<<x<<' ';cout<<'\n';}
import sys
def z_function(s):
z=[0]*len(s);l=r=0
for i in range(1,len(s)):
if i<r:z[i]=min(r-i,z[i-l])
while i+z[i]<len(s) and s[z[i]]==s[i+z[i]]:z[i]+=1
if i+z[i]>r:l,r=i,i+z[i]
return z
def find_all(t,p):
if not p:return list(range(len(t)+1))
s=p+'\0'+t;z=z_function(s);return [i-len(p)-1 for i in range(len(p)+1,len(s)) if z[i]>=len(p)]
if __name__=='__main__':
q=sys.stdin.read().splitlines();t,p=(q+[''])[:2] if q else ('ababa','aba');a=find_all(t,p);print(len(a));print(*a)
Hàm dựng Z tốn O(n) thời gian, O(n) bộ nhớ. Bài tìm mẫu chạy O(n+m), không có xác suất va chạm. So với KMP, Z tạo một mảng trên xâu ghép; KMP chỉ cần pi của mẫu và có thể giữ trạng thái thuận tiện khi văn bản đến theo luồng.
Chủ đề này nằm trong Buổi 09 - KMP, Z-function, Trie & Rolling Hash của Tài năng lập trình. Xem đề cương
Bất biến cần nhìn khi gỡ lỗi
Sau mỗi vòng, [l,r) phải bằng tiền tố s[0:r-l), và không cửa sổ nào đã xét có biên phải lớn hơn r. Khi sao chép z[i-l], chỉ phần nằm trong cửa sổ được tin. Nếu giá trị sao chép nhỏ hơn r-i, nó hoàn toàn nằm trong vùng đã biết và không cần mở rộng; nếu chạm biên, vòng while sẽ kiểm phần mới.
Với r là biên nửa mở, giá trị khởi tạo phải là min(r-i, z[i-l]). Nếu chép công thức của biên đóng min(r-i+1, z[i-l]), z[i] có thể bị đặt lớn hơn thực tế: với aaa, mảng thành 0,2,2 thay vì 0,2,1. Còn viết i<=r thì vô hại, vì khi i=r giá trị khởi tạo bằng 0.
Các lỗi phổ biến khác gồm dùng separator thật sự có trong dữ liệu và quên trừ m+1 khi đổi vị trí về text. Vì separator không có trong text, z[i] ở phần text không bao giờ vượt m, nên điều kiện z[i]==m và z[i]>=m cho cùng kết quả; code dùng >= chỉ để an toàn.
Z còn giải được gì?
Để tìm các độ dài vừa là tiền tố vừa là hậu tố, xét vị trí i có i+z[i]=n; độ dài là z[i]. Để tìm chu kỳ, kiểm các vị trí mà phần còn lại được tiền tố phủ phù hợp. Để đếm số lần mỗi tiền tố xuất hiện, đếm phân phối các giá trị Z rồi cộng hậu tố theo độ dài, sau đó cộng thêm 1 cho chính lần xuất hiện ở vị trí 0 (vì bài quy ước z[0]=0).
Trong bài nối hai xâu, Z cho biết tiền tố của một xâu khớp bao xa tại từng điểm của xâu kia. Trong nén xâu, các đoạn lặp liên tiếp có thể được nhận diện từ mảng Z, nhưng phải phân biệt “có cùng tiền tố” với “toàn xâu là lũy thừa của một khối”.
Tự kiểm tra mảng Z và hàm tìm mẫu
Để chắc chắn cách cập nhật cửa sổ [l, r) không bị lệch một đơn vị, bạn có thể viết một hàm tính mảng Z trực tiếp bằng vòng lặp: tại mỗi vị trí i, đếm số ký tự trùng liên tiếp giữa s[0..] và s[i..]. Hãy đối chiếu kết quả trên các ca như ababa tìm aba, aaaaa tìm aa, mẫu không xuất hiện trong văn bản và trường hợp mẫu rỗng. Danh sách vị trí tìm được cũng như từng phần tử z[i] phải khớp hoàn toàn giữa hai cách tính.
Một bài thử rất mạnh khác là duyệt mọi xâu nhị phân độ dài tối đa 8 trên hai ký tự {a, b}, tính mảng z bằng cả thuật toán cửa sổ tuyến tính lẫn vòng lặp đếm trực tiếp. Cách thử trên xâu nhị phân ngắn này buộc chương trình đi qua cả hai nhánh quan trọng: trường hợp z[i - l] < r - i (kết thúc hoàn toàn bên trong cửa sổ) và trường hợp z[i - l] >= r - i (chạm biên phải và phải mở rộng tiếp qua r).
Bảng phân biệt ba tình huống của cửa sổ Z
| Vị trí i | Quan hệ với r | Cách khởi tạo z[i] |
|---|---|---|
| i ở ngoài cửa sổ | i >= r |
bắt đầu từ 0 |
| i ở trong, giá trị cũ chưa chạm biên | z[i-l] < r-i |
chép nguyên giá trị cũ |
| i ở trong, giá trị cũ chạm biên | z[i-l] >= r-i |
lấy r-i rồi mở rộng |
Tự chạy bảng trên aabcaabxaaaz. Ở mỗi dòng, ghi [l,r) trước và sau khi xử lý; nếu r giảm thì cài đặt đã phá bất biến. Sau đó tạo các xâu nhị phân dài tối đa 8, tính Z bằng vòng lặp chậm tại từng vị trí và so cả mảng. Các ca aaaaaa, ababab và abcabcx lần lượt kiểm vùng lặp dày, chu kỳ và lần mở rộng dừng ngay sau biên.
Với bài tìm mẫu, kiểm thêm ký tự phân cách không có trong dữ liệu. Nếu đầu vào có thể chứa mọi byte, không nên ghép bằng một byte tùy ý; hãy dùng cấu trúc số nguyên với giá trị phân cách nằm ngoài bảng ký tự.
Khi Z thuận tiện hơn pi
Z trả lời trực tiếp câu hỏi “tiền tố khớp bao xa từ vị trí i”, vì vậy dễ dùng cho bài kiểm từng phép dịch, tìm đoạn lặp từ đầu hoặc so một mẫu với mọi vị trí. Pi trả lời “biên dài nhất của tiền tố kết thúc tại i”, phù hợp hơn cho chuỗi biên lồng nhau và máy trạng thái.
Ví dụ muốn tìm mọi độ dài tiền tố cũng là hậu tố, với Z chỉ cần xét các i thỏa i+z[i]=n. Muốn đếm số lần tiền tố dài k xuất hiện, đếm các Z có giá trị ít nhất k rồi cộng 1 cho chính lần xuất hiện ở vị trí 0. Khi cần tất cả k, sắp hoặc cộng dồn tần suất theo độ dài để tránh một vòng quét cho từng k.
Đừng suy rằng Z lớn tại i nghĩa đoạn lặp có chu kỳ i. Nó chỉ chứng minh phần bắt đầu ở i giống tiền tố trong z[i] ký tự. Điều kiện chu kỳ còn phụ thuộc độ dài toàn xâu và cách các khối phủ nhau. Luôn viết mệnh đề cần chứng minh trước khi chuyển một giá trị Z thành kết luận mạnh hơn.
Luyện ngay trên Big-O Coding
Hai bài dưới đây luyện đúng thông tin mà mảng Z trả lời: độ dài vừa là tiền tố vừa là hậu tố (các i có i + z[i] = n) và số lần xuất hiện của từng tiền tố.
Câu hỏi thường gặp
Có cần nhớ hai biến l và r không?
Cần hiểu chúng là cửa sổ khớp tiền tố xa nhất. Từ ý nghĩa đó, công thức min(r-i,z[i-l]) được suy ra.
Z-function có bị va chạm như hash không?
Không. Nó so ký tự trực tiếp và cho kết quả xác định trong O(n).
Chọn KMP hay Z khi tìm mẫu?
Cả hai đều tuyến tính. Chọn KMP nếu cần trạng thái luồng hoặc thông tin biên; chọn Z nếu các câu hỏi xoay quanh độ khớp với tiền tố tại mọi vị trí.
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


