KMP và Z-function

Mức độ: Chuyên sâu

Tìm mọi vị trí mẫu p xuất hiện trong xâu t. So từng vị trí mất |t| × |p| bước. Hash làm nhanh nhưng có thể (rất hiếm) trùng. KMP và Z-function làm trong |t| + |p| bước và luôn đúng, nhờ tận dụng phần đã khớp thay vì so lại từ đầu.

Hàm tiền tố

pi[i] là độ dài biên dài nhất của i + 1 ký tự đầu s[0..i]: tiền tố dài nhất (không phải cả đoạn) đồng thời là hậu tố của đoạn đó.

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

pi[6] = 3 vì aba vừa là tiền tố vừa là hậu tố của abacaba.

Cách tính: biết pi[i - 1] = k (k ký tự đầu khớp với k ký tự kết thúc ở i - 1). Nếu s[i] = s[k] thì biên dài thêm 1: pi[i] = k + 1. Nếu không, thử biên ngắn hơn: biên tiếp theo của s[0..i - 1] là biên của s[0..k - 1], tức là k = pi[k - 1]. Lặp đến khi khớp hoặc k = 0.

Mỗi bước k tăng nhiều nhất 1, nên tổng số lần giảm không quá n: cả việc tính chỉ khoảng 2n bước.

Python

def ham_tien_to(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        k = pi[i - 1]
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]          # thử biên ngắn hơn
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi

t = input().strip()
p = input().strip()
pi = ham_tien_to(p + '#' + t)      # '#' không có trong t, p
m = len(p)
vi_tri = [i - 2 * m + 1 for i in range(len(pi)) if pi[i] == m]   # vị trí bắt đầu trong t, đánh số từ 1
print(*vi_tri if vi_tri else [-1])

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> hamTienTo(const string &s) {
    vector<int> pi(s.size(), 0);
    for (size_t i = 1; i < s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // thử biên ngắn hơn
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

int main() {
    string t, p;
    cin >> t >> p;
    int m = p.size();
    vector<int> pi = hamTienTo(p + '#' + t);          // '#' không có trong t, p
    vector<int> viTri;
    for (int i = 0; i < (int)pi.size(); i++)
        if (pi[i] == m) viTri.push_back(i - 2 * m + 1);
    if (viTri.empty()) viTri.push_back(-1);
    for (size_t k = 0; k < viTri.size(); k++) cout << viTri[k] << (k + 1 < viTri.size() ? ' ' : '\n');
    return 0;
}

Tìm mẫu

Ghép xâu p + ’#’ + t (ký tự # không có trong cả hai xâu). Ở một vị trí trong phần t, pi bằng |p| khi và chỉ khi |p| ký tự kết thúc ở đó đúng bằng p. Ký tự # ngăn không cho biên dài hơn |p|.

Z-function

z[i] là độ dài tiền tố chung dài nhất của s và s[i:] (đoạn bắt đầu tại i). Quy ước z[0] = 0.

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

z[4] = 3 vì s[4:] = aba khớp 3 ký tự đầu của s.

Cách tính: giữ “cửa sổ khớp” [l, r) là đoạn khớp với tiền tố mà r xa nhất đã biết. Ở vị trí i nằm trong cửa sổ, s[i:r] giống s[i - l : r - l], nên z[i] ít nhất là min(r - i, z[i - l]); chỉ cần so tiếp các ký tự sau r. Mỗi lần so thành công r tăng lên, nên cả bài khoảng 2n bước.

def ham_z(s):
    n = len(s)
    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

Tìm mẫu bằng Z: tính Z của p + ’#’ + t, vị trí có z bằng |p| là chỗ p xuất hiện.

Luyện tập

Gồm 12 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hàm tiền tố và Z-function

Bài 1. Tính hàm tiền tố

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). In ra pi[0], pi[1], …, pi[|s| - 1], với pi[i] là độ dài biên dài nhất của s[0..i] (tiền tố dài nhất, khác cả đoạn, đồng thời là hậu tố).

Ví dụ: nhập abacaba thì in ra 0 0 1 0 1 2 3.

Kiểm tra: nhập aabaaabaaab.

Xem đáp số

0 1 0 1 2 2 3 4 5 6 7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Tính Z-function

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). In ra z[0], z[1], …, z[|s| - 1], với z[0] = 0 và z[i] là độ dài tiền tố chung dài nhất của s và s[i:].

Ví dụ: nhập abacaba thì in ra 0 0 1 0 3 0 1.

Kiểm tra: nhập aabaaabaaab.

Xem đáp số

0 1 0 2 7 1 0 2 3 1 0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Mọi vị trí xuất hiện

Dòng đầu là xâu t, dòng thứ hai là mẫu p (chữ cái thường, 1 ≤ |p| ≤ |t| ≤ 10⁶). In ra mọi vị trí (đánh số từ 1) mà p xuất hiện bắt đầu từ đó trong t, theo thứ tự tăng dần, hoặc -1 nếu không có.

Ví dụ:

Nhập	In ra
abababa aba	1 3 5

Kiểm tra: nhập

bumbiibumbiibumbii
bii

Xem đáp số

4 10 16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Biên và chu kỳ

Bài 4. Mọi biên của xâu

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). In ra theo thứ tự tăng dần mọi độ dài k (1 ≤ k nhỏ hơn |s|) mà k ký tự đầu bằng k ký tự cuối, hoặc -1 nếu không có.

Ví dụ: nhập abacaba thì in ra 1 3.

Kiểm tra: nhập aabaaabaabaa.

Xem đáp số

1 2 5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Chu kỳ ngắn nhất

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). Tìm độ dài k nhỏ nhất sao cho s[i] = s[i + k] với mọi i hợp lệ, tức là s là đoạn đầu của khối dài k viết lặp lại (k không cần là ước của |s|). In ra k.

Ví dụ: nhập abcabca thì in ra 3.

Kiểm tra: nhập aabaaabaaabaa.

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Số lần xuất hiện của mỗi tiền tố

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). Với mỗi k từ 1 đến |s|, in ra số lần tiền tố dài k của s xuất hiện trong s (tính cả lần ở đầu, các lần được chồng lên nhau).

Ví dụ: nhập abacaba thì in ra 4 2 2 1 1 1 1.

Kiểm tra: nhập aabaaabaa.

Xem đáp số

7 4 2 2 2 1 1 1 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Mật khẩu ẩn giữa xâu

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). Tìm đoạn x dài nhất vừa là tiền tố, vừa là hậu tố của s, và còn xuất hiện ở giữa s (không phải ở đầu, không phải ở cuối). In ra x, hoặc NONE nếu không có.

Ví dụ: nhập fixprefixsuffix thì in ra fix.

Kiểm tra: nhập abcdabcabcdabc.

Xem đáp số

abc

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Ghép xâu để tìm kiếm

Bài 8. Xâu đối xứng ngắn nhất bằng cách thêm vào đầu

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). Thêm ít ký tự nhất vào đầu s để được xâu đối xứng. In ra số ký tự phải thêm.

Ví dụ: nhập aacecaaa thì in ra 1.

Kiểm tra: nhập abcdcbaxyz.

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Ghép hai xâu chồng nhau

Nhập hai xâu a và b trên hai dòng (chữ cái thường, mỗi xâu dài từ 1 đến 10⁶). Ghép b vào sau a, cho phép phần đầu của b trùng với phần cuối của a (chỉ viết một lần). In ra độ dài ngắn nhất của xâu ghép.

Ví dụ:

Nhập	In ra
abcde cdefg	7

Kiểm tra: nhập

bumbiibumb
biibumbii

Xem đáp số

12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Mẫu trên vòng tròn

Xâu t được viết trên một vòng tròn (sau ký tự cuối là ký tự đầu). Dòng đầu là t, dòng thứ hai là mẫu p (chữ cái thường, 1 ≤ |p| ≤ |t| ≤ 10⁶). In ra số vị trí bắt đầu trên vòng tròn mà đọc |p| ký tự theo chiều kim đồng hồ được đúng p.

Ví dụ:

Nhập	In ra
abcab bca	1

Kiểm tra: nhập

abaab
aba

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Ghép từ các tiền tố

Dòng đầu là xâu p, dòng thứ hai là xâu t (chữ cái thường, mỗi xâu dài từ 1 đến 10⁶). Viết t thành ghép của ít đoạn nhất, mỗi đoạn là một tiền tố (khác rỗng) của p. In ra số đoạn ít nhất, hoặc -1 nếu không viết được.

Ví dụ:

Nhập	In ra
abcab ababcaa	3

Kiểm tra: nhập

bumbii
bumbubbumbibu

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Xoay vòng nhỏ nhất theo từ điển

Nhập xâu s (chữ cái thường, 1 ≤ |s| ≤ 10⁶). Trong |s| cách xoay s (chuyển k ký tự đầu xuống cuối, 0 ≤ k nhỏ hơn |s|), in ra cách xoay cho xâu nhỏ nhất theo thứ tự từ điển (nếu nhiều k cùng cho xâu đó, chọn k nhỏ nhất) dưới dạng số k.

Ví dụ: nhập bcaab thì in ra 2.

Kiểm tra: nhập cabcabcab.

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.