🎯 Mục tiêu bài học

• Hiểu cơ chế tìm mẫu (pattern matching) trong chuỗi.
• Biết cách hoạt động của thuật toán KMP và Z-Algorithm.
• So sánh tốc độ giữa tìm kiếm tuyến tính và KMP.

📘 1️⃣ Giới thiệu bài toán

Cho chuỗi T (văn bản) và chuỗi P (mẫu). Tìm mọi vị trí i sao cho T[i..i+|P|-1] = P.

📘 2️⃣ Thuật toán KMP

KMP tính trước mảng LPS (Longest Prefix Suffix) để khi lệch không cần quay lại toàn bộ mẫu.

🌿 C++

vector<int> buildLPS(string p){
    int n=p.size(); vector<int> lps(n);
    for(int i=1,len=0;i<n;){
        if(p[i]==p[len]) lps[i++]=++len;
        else if(len) len=lps[len-1];
        else lps[i++]=0;
    }
    return lps;
}

🌿 Python

def build_lps(p):
    n=len(p);lps=[0]*n;length=0;i=1
    while i<n:
        if p[i]==p[length]:
            length+=1;lps[i]=length;i+=1
        elif length: length=lps[length-1]
        else: i+=1
    return lps

📘 3️⃣ Z-Algorithm (tìm mẫu bằng Z-array)

Z-Algorithm tạo mảng Z[i] = độ dài đoạn khớp giữa T[i..] và T. Ứng dụng: tìm P trong T bằng cách nối P#$T.

def Z_algorithm(s):
    n=len(s);Z=[0]*n;l=r=0
    for i in range(1,n):
        if i<=r: Z[i]=min(r-i+1,Z[i-l])
        while i+Z[i]<n and s[Z[i]]==s[i+Z[i]]:
            Z[i]+=1
        if i+Z[i]-1>r: l=i;r=i+Z[i]-1
    return Z
print(Z_algorithm("aabxaayaab"))

🧩 Bài tập luyện tập

1. In tất cả vị trí xuất hiện của P trong T bằng KMP.
2. So sánh thời gian chạy giữa KMP và tìm tuyến tính cho n = 10⁶.
3. Sử dụng Z-Algorithm để đếm số lần P xuất hiện trong T.

t="ababcababcabc"; p="ababc"
lps=build_lps(p)
i=j=0
while i<len(t):
    if t[i]==p[j]: i+=1; j+=1
    if j==len(p):
        print("found at",i-j)
        j=lps[j-1]
    elif i<len(t) and t[i]!=p[j]:
        j=lps[j-1] if j else i+1