Elearning CodePath – CTP Online Judge

🎯 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 buildLPS(string p){
    int n=p.size(); vector lps(n);
    for(int i=1,len=0;i



🌿 Python
def build_lps(p):
    n=len(p);lps=[0]*n;length=0;i=1
    while i




📘 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]r: l=i;r=i+Z[i]-1
    return Z
print(Z_algorithm("aabxaayaab"))



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

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


💡 Lời giải 1
t="ababcababcabc"; p="ababc"
lps=build_lps(p)
i=j=0
while i