Naive string matching — vì sao O(n·m) chậm

TL;DR: Naive matching trượt pattern qua text từ trái sang phải, mỗi vị trí so từng ký tự. Worst-case O(n·m) xảy ra khi text lặp một ký tự (ví dụ "aaaa...a") và pattern gần như khớp hoàn toàn rồi lệch ở ký tự cuối — mỗi vị trí khởi đầu đều so gần hết pattern. Nhưng với văn bản tự nhiên và bảng chữ cái lớn, lệch xảy ra sớm nên thực nghiệm gần O(n). Hiểu rõ điểm lãng phí của naive — lùi con trỏ text và so lại đoạn đã biết — chính là chìa khoá để thấy tại sao KMP và Rabin-Karp ra đời.

Hãy tưởng tượng bạn cần kiểm tra xem một đoạn DNA dài 10 triệu base pair có chứa một chuỗi mồi (primer) dài 20 ký tự không. Cách đơn giản nhất: đặt chuỗi mồi vào vị trí 0, so từng ký tự, rồi trượt sang 1, so lại, tiếp tục cho đến cuối. Đây chính là naive matching — trực quan, dễ cài đặt, và trong trường hợp xấu nhất tốn tới 200 triệu phép so sánh. Bài này phân tích cơ chế, worst-case, và điều kiện naive vẫn đủ dùng trước khi ta đào sâu vào KMP ở bài tiếp theo.

1. Cơ chế trượt cửa sổ

Naive matching duy trì một cửa sổ (window) dài m (độ dài pattern) trượt qua text dài n. Với mỗi vị trí khởi đầu i từ 0 đến n - m, thuật toán so từng ký tự P[j] với T[i + j] cho j từ 0 đến m - 1. Nếu tất cả khớp → tìm thấy. Nếu có ký tự lệch → dịch cửa sổ sang phải 1 ô và bắt đầu lại từ j = 0.

Điểm mấu chốt cần nhớ: khi lệch tại j = k, ta vứt bỏ mọi thông tin về k ký tự vừa khớp — con trỏ text lùi về i + 1 và so lại từ đầu. Đây chính là "lãng phí" mà KMP sẽ loại bỏ.

function naiveSearch(T, P):
    n <- T.length
    m <- P.length
    results <- rỗng
    for i from 0 to n - m:            -- dịch cửa sổ qua text
        j <- 0
        while j < m and T[i + j] = P[j]:   -- so từng ký tự
            j <- j + 1
        if j = m:                      -- khớp toàn bộ pattern
            thêm i vào results
    return results
// Time: O(n·m) worst-case  Space: O(1) ngoài kết quả

1.1 Trace nhỏ: T = "ABCABD", P = "ABD"

flowchart LR
    INIT(["i=0, j=0"]) --> CMP{"T[i+j] = P[j]?"}
    CMP -->|"khớp, j < m-1"| NEXT["j++"]
    NEXT --> CMP
    CMP -->|"khớp, j = m-1"| FOUND(["báo i; i++, j=0"])
    FOUND --> CHECK
    CMP -->|"lệch"| SHIFT["i++, j=0<br/>(bỏ j ký tự đã biết)"]
    SHIFT --> CHECK{"i ≤ n-m?"}
    CHECK -->|"còn"| CMP
    CHECK -->|"hết"| DONE(["kết thúc"])

2. Worst-case O(n·m) — giải phẫu

Worst-case xảy ra khi text và pattern đều có độ lặp cao. Ví dụ kinh điển:

• Text T = "aaa...a" (n ký tự a)
• Pattern P = "aaa...ab" (m-1 ký tự a + 1 ký tự b)

Với mỗi vị trí i (từ 0 đến n - m), thuật toán khớp được m - 1 ký tự a trước khi lệch ở ký tự cuối b. Số phép so sánh cho vị trí đó là m. Tổng cộng (n - m + 1) × m phép so sánh — xấp xỉ n·m khi m nhỏ so n.

Ví dụ cụ thể: n = 1 000 000, m = 1 000. Worst-case: 10^9 phép so sánh. Với tốc độ 10^9 thao tác/giây, mất ~1 giây cho mỗi lần tìm kiếm — không chấp nhận được cho hệ thống thời gian thực.

sequenceDiagram
    participant T as Text "aaaab"
    participant P as Pattern "aab"
    Note over T,P: i=0: so A→A, A→A, A≠B (2 khớp + 1 lệch = 3 phép so)
    Note over T,P: i=1: so A→A, A→A, A≠B (2 khớp + 1 lệch = 3 phép so)
    Note over T,P: i=2: so A→A, A→A, B→B (3 khớp = KHỚP hoàn toàn, 3 phép so)
    Note over T,P: Tổng: 3+3+3 = 9 phép so sánh

2.1 Bảng phân tích số phép so sánh

3. Khi nào naive vẫn đủ tốt

Mặc dù worst-case O(n·m) đáng ngại về lý thuyết, naive thường đủ tốt trong thực tế khi:

Bảng chữ cái lớn, pattern không lặp. Tìm từ tiếng Anh trong văn bản — lệch xảy ra ở ký tự thứ 1 hoặc 2 của pattern với xác suất cao. Trung bình mỗi vị trí chỉ cần ~1-2 phép so sánh, tổng ~1.1·n.

Text và/hoặc pattern ngắn. Nếu n < 1000 hoặc m < 10, ngay cả O(n·m) cũng tính xong trong microsecond. Overhead cài đặt KMP (xây bảng lps) lúc này không đáng.

Tìm một lần, không lặp. Nếu pattern thay đổi mỗi lần truy vấn (như tìm kiếm người dùng nhập), chi phí preprocessing O(m) của KMP được hoàn vốn ngay. Nhưng nếu chỉ tìm 1-2 lần rồi bỏ, naive đơn giản hơn.

Môi trường nhúng / bộ nhớ hạn chế. Naive chỉ cần O(1) bộ nhớ phụ. KMP cần O(m) cho bảng lps; Rabin-Karp cần xử lý số học modular.

4. Vì sao lùi con trỏ text là lãng phí

Đây là điểm quan trọng nhất để hiểu tại sao KMP ra đời. Khi naive lệch sau khi khớp j ký tự, nó biết chắc:

T[i], T[i+1], ..., T[i+j-1] khớp với P[0], P[1], ..., P[j-1]

Nhưng thay vì tận dụng thông tin này, naive quay con trỏ text về i + 1 và so lại từ đầu — bỏ qua j ký tự đã biết. KMP hỏi: "Nếu pattern có tiền tố trùng với hậu tố của đoạn vừa khớp, tại sao không dịch thẳng để tận dụng?"

flowchart TD
    A["Đã khớp: T[i..i+j-1] = P[0..j-1]"] --> B{"Naive"}
    A --> C{"KMP"}
    B --> D["Lùi về T[i+1]<br/>So lại từ P[0]<br/>⇒ lãng phí j bước"]
    C --> E["Giữ nguyên con trỏ text<br/>Dịch pattern dùng lps[j-1]<br/>⇒ không lùi"]
    D --> F["O(n·m) worst-case"]
    E --> G["O(n+m) tất định"]

5. Pitfall

Pitfall 1 — Điều kiện vòng ngoài sai: i < n thay vì i <= n - m

-- SAI: có thể đọc ngoài biên T[i + j] với i+j >= n
for i from 0 to n - 1:
    for j from 0 to m - 1:
        if T[i + j] = P[j]: ...    -- NGUY HIỂM khi i + j >= n

-- ĐÚNG: dừng khi không còn đủ chỗ cho pattern
for i from 0 to n - m:
    ...

Khi i > n - m, cửa sổ vượt quá cuối text — không thể khớp đủ m ký tự. Giới hạn đúng là i chạy đến n - m (bao gồm).

Pitfall 2 — Trả về ngay khi tìm thấy lần đầu thay vì tiếp tục

-- SAI khi cần tìm TẤT CẢ lần xuất hiện:
if j = m:
    return i    -- bỏ sót các lần sau

-- ĐÚNG: ghi nhận và tiếp tục
if j = m:
    thêm i vào results
    -- tiếp tục vòng for

Trường hợp điển hình: đếm số lần từ xuất hiện trong văn bản, hoặc tìm tất cả vị trí primer trong genome.

Pitfall 3 — Nhầm worst-case với average-case cho văn bản tự nhiên

Naive thực tế thường chạy gần O(n) trên văn bản tiếng Anh/Việt — lệch sớm ở ký tự đầu hoặc thứ hai. Lầm lẫn này dẫn đến hai hướng sai: (a) tối ưu hóa quá sớm khi không cần, hoặc (b) dùng naive cho dữ liệu lặp cao (DNA, nhị phân) mà không biết worst-case thực sự đạt được.

6. Liên hệ các bài khác

• KMP — failure function & matching O(n+m): Bài kế tiếp trực tiếp — KMP sinh ra để vá đúng điểm lãng phí của naive (lùi con trỏ text). Hiểu rõ "lãng phí ở đâu" trong bài này là tiền đề để thấy vì sao failure function giải quyết được.
• Rabin-Karp — rolling hash cho đa mẫu: Hướng tiếp cận hoàn toàn khác — thay vì tối ưu bước dịch, dùng hash để bỏ qua phần lớn các vị trí không khớp. So sánh với naive để thấy tradeoff hash vs so ký tự trực tiếp.
• Big-O từ bản chất: Phân tích O(n·m) của naive là ví dụ điển hình về vòng lồng nhau và tầm quan trọng của phân tích worst vs average-case — nên đọc nếu chưa vững Big-O.

📚 Deep Dive

Tóm tắt

• Naive matching trượt pattern qua text từ trái sang phải, so từng ký tự tại mỗi vị trí — O(1) bộ nhớ, đơn giản để cài đặt.
• Worst-case O(n·m) xảy ra khi text và pattern đều lặp cao (vd: text "aaaa...a", pattern "aaa...ab").
• Average-case trên văn bản tự nhiên gần O(n) vì lệch xảy ra sớm ở ký tự đầu.
• Naive vẫn đủ tốt khi: bảng chữ cái lớn, n·m nhỏ hơn ~10^7, pattern thay đổi liên tục, hoặc bộ nhớ hạn chế.
• Điểm lãng phí cốt lõi: khi lệch sau j ký tự khớp, naive lùi con trỏ text về i+1 và bỏ thông tin về j ký tự đã biết.
• KMP loại bỏ chính xác điểm lãng phí đó bằng failure function — con trỏ text không bao giờ lùi.

Tự kiểm tra

Bài tiếp theo: KMP — failure function & matching O(n+m)