KMP — Knuth-Morris-Pratt

Năm 2023, một kỹ sư tại Elastic báo cáo rằng hệ thống log search xử lý 2TB log mỗi ngày bị timeout liên tục khi pattern chứa nhiều ký tự lặp. Nguyên nhân: engine vẫn dùng naive search O(n × m) cho một số edge case. Sau khi chuyển sang KMP-based matching, latency giảm từ 12 giây xuống 40ms — cải thiện 300 lần.

KMP là thuật toán tìm kiếm chuỗi đầu tiên đạt được worst-case O(n + m), được Knuth, Morris và Pratt công bố năm 1977. Ý tưởng cốt lõi chỉ có một câu: khi mismatch xảy ra, đừng bỏ phí thông tin về những ký tự đã khớp. Thay vì quay lại đầu pattern, KMP sử dụng một bảng tiền xử lý (failure function) để nhảy thẳng đến vị trí an toàn nhất.

Hiểu sâu failure function không chỉ giúp bạn nắm KMP, mà còn mở khóa tư duy xây dựng Aho-Corasick automaton — thuật toán multi-pattern matching đang chạy trong mọi hệ thống antivirus và IDS hiện đại.

Bức tranh tư duy

Hình dung bạn đang đọc một cuốn tiểu thuyết dài và cần tìm câu "anh ấy anh ấy đi". Mắt bạn quét từng dòng. Khi đọc được "anh ấy anh ấy dừng" — sai ở ký tự cuối. Một người đọc ngây thơ sẽ quay lại từ đầu, bắt đầu tìm lại từ ký tự thứ hai. Nhưng bạn — một người đọc thông minh — nhận ra rằng phần "anh ấy" vừa đọc xong cũng chính là phần mở đầu của cụm cần tìm. Bạn không quay lại, mà tiếp tục từ vị trí đó.

Đó chính xác là cách KMP hoạt động. Con trỏ trên text chỉ tiến, không bao giờ lùi. Chỉ con trỏ trên pattern được điều chỉnh — nhưng nhảy về đâu? Về vị trí mà prefix dài nhất của phần đã khớp trùng với suffix của nó.

CON TRỎ TEXT CHỈ TIẾN, KHÔNG BAO GIỜ LÙI

Text:     a b a b a c a b a b a b c
Pattern:  a b a b a b c
                      ↑ mismatch tại index 5 (c ≠ b)

Naive:    lùi text về index 1, thử lại từ đầu

KMP:      text giữ nguyên vị trí!
          pattern nhảy: j = failure[4] = 3
          (vì "aba" vừa là prefix vừa là suffix của "ababa")

Text:     a b a b a c a b a b a b c
Pattern:      a b a b a b c
              ↑ tiếp tục so sánh từ j=3

Bảng failure function (hay LPS — Longest Proper Prefix which is also Suffix) chính là "bộ nhớ thông minh" cho phép KMP tận dụng mọi thông tin đã thu thập được, không lãng phí một phép so sánh nào.

Cốt lõi kỹ thuật

Bảng Failure Function (LPS Array)

Với mỗi vị trí i trong pattern, LPS[i] lưu độ dài prefix dài nhất cũng là suffix (proper — không tính chính chuỗi đó) của pattern[0..i].

Pattern:  a  b  a  b  a  b  c
Index:    0  1  2  3  4  5  6
LPS:      0  0  1  2  3  4  0

Giải thích:
  i=0: "a"         → không có proper prefix = suffix → 0
  i=1: "ab"        → "a" ≠ "b"                       → 0
  i=2: "aba"       → "a" = "a" ✓                     → 1
  i=3: "abab"      → "ab" = "ab" ✓                   → 2
  i=4: "ababa"     → "aba" = "aba" ✓                 → 3
  i=5: "ababab"    → "abab" = "abab" ✓               → 4
  i=6: "abababc"   → không prefix nào = suffix        → 0

Ý nghĩa: khi mismatch tại vị trí j, ta biết pattern[0..j-1] đã khớp với text. LPS[j-1] cho biết bao nhiêu ký tự đầu pattern vẫn khớp — ta nhảy j = LPS[j-1] thay vì j = 0.

Xây dựng bảng LPS — O(m)

Thuật toán xây LPS sử dụng chính kỹ thuật KMP trên pattern với chính nó:

C++

#include <vector>
#include <string>

std::vector<int> buildLPS(const std::string& pattern) {
    int m = pattern.size();
    std::vector<int> lps(m, 0);
    int len = 0; // độ dài prefix-suffix trước đó
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else if (len != 0) {
            // điểm mấu chốt: fallback, KHÔNG tăng i
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

Python

from typing import List

def build_lps(pattern: str) -> List[int]:
    m = len(pattern)
    lps = [0] * m
    length = 0  # độ dài prefix-suffix trước đó
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            # điểm mấu chốt: fallback, KHÔNG tăng i
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

Java

public static int[] buildLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0;
    int i = 1;

    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

Go

func buildLPS(pattern string) []int {
    m := len(pattern)
    lps := make([]int, m)
    length := 0
    i := 1

    for i < m {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else if length != 0 {
            length = lps[length-1]
        } else {
            lps[i] = 0
            i++
        }
    }
    return lps
}

Thuật toán KMP Search — O(n + m)

Hai con trỏ: i trên text (chỉ tiến), j trên pattern (có thể lùi qua LPS):

C++

#include <vector>
#include <string>

std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
    int n = text.size(), m = pattern.size();
    std::vector<int> lps = buildLPS(pattern);
    std::vector<int> result;

    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == m) {
                result.push_back(i - j);
                j = lps[j - 1]; // tìm overlapping match
            }
        } else if (j != 0) {
            j = lps[j - 1]; // fallback — KHÔNG lùi i
        } else {
            i++;
        }
    }
    return result;
}

Python

from typing import List

def kmp_search(text: str, pattern: str) -> List[int]:
    if not pattern or not text or len(pattern) > len(text):
        return []

    n, m = len(text), len(pattern)
    lps = build_lps(pattern)
    result: List[int] = []

    i = 0  # con trỏ text — CHỈ TIẾN
    j = 0  # con trỏ pattern — có thể lùi qua LPS

    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                result.append(i - j)
                j = lps[j - 1]
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1
    return result

Java

import java.util.ArrayList;
import java.util.List;

public static List<Integer> kmpSearch(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    int[] lps = buildLPS(pattern);
    List<Integer> result = new ArrayList<>();

    int i = 0, j = 0;
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
            if (j == m) {
                result.add(i - j);
                j = lps[j - 1];
            }
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return result;
}

Go

func kmpSearch(text, pattern string) []int {
    n, m := len(text), len(pattern)
    if m == 0 || n < m {
        return nil
    }
    lps := buildLPS(pattern)
    var result []int

    i, j := 0, 0
    for i < n {
        if text[i] == pattern[j] {
            i++
            j++
            if j == m {
                result = append(result, i-j)
                j = lps[j-1]
            }
        } else if j != 0 {
            j = lps[j-1]
        } else {
            i++
        }
    }
    return result
}

Demo từng bước

Text:    A B A A C A B A A B
Pattern: A B A A B          LPS: [0, 0, 1, 1, 2]

Bước  i  j  text[i] pat[j]  Hành động
────  ─  ─  ──────  ──────  ──────────────────────────
  1   0  0    A       A     match → i=1, j=1
  2   1  1    B       B     match → i=2, j=2
  3   2  2    A       A     match → i=3, j=3
  4   3  3    A       A     match → i=4, j=4
  5   4  4    C       B     mismatch, j>0 → j=LPS[3]=1
  6   4  1    C       B     mismatch, j>0 → j=LPS[0]=0
  7   4  0    C       A     mismatch, j=0 → i=5
  8   5  0    A       A     match → i=6, j=1
  9   6  1    B       B     match → i=7, j=2
 10   7  2    A       A     match → i=8, j=3
 11   8  3    A       A     match → i=9, j=4
 12   9  4    B       B     match → i=10, j=5 → TÌM THẤY tại 5 ✓

Thực chiến

Tình huống: Quét log server tìm error pattern

Bối cảnh: Hệ thống monitoring cần quét 50GB access log mỗi ngày để phát hiện dấu hiệu tấn công SQL injection. Log được stream từ Kafka, không thể lưu toàn bộ vào RAM.

Mục tiêu: Tìm mọi vị trí xuất hiện pattern "UNION SELECT" trong stream, latency < 1ms per chunk.

C++

#include <string>
#include <vector>
#include <functional>

class StreamingKMP {
    std::string pattern_;
    std::vector<int> lps_;
    int j_ = 0; // trạng thái pattern pointer giữa các chunk

public:
    explicit StreamingKMP(const std::string& pattern)
        : pattern_(pattern), lps_(buildLPS(pattern)) {}

    // Xử lý từng chunk, giữ state giữa các lần gọi
    std::vector<size_t> processChunk(
        const std::string& chunk, size_t globalOffset) {
        std::vector<size_t> matches;
        int n = chunk.size(), m = pattern_.size();

        for (int i = 0; i < n; ) {
            if (chunk[i] == pattern_[j_]) {
                i++;
                j_++;
                if (j_ == m) {
                    matches.push_back(globalOffset + i - m);
                    j_ = lps_[j_ - 1];
                }
            } else if (j_ != 0) {
                j_ = lps_[j_ - 1];
            } else {
                i++;
            }
        }
        return matches;
    }

    void reset() { j_ = 0; }
};

Python

from typing import List, Generator

class StreamingKMP:
    """KMP cho streaming data — giữ state giữa các chunk."""

    def __init__(self, pattern: str) -> None:
        self.pattern = pattern
        self.lps = build_lps(pattern)
        self.j = 0  # trạng thái giữa các chunk

    def process_chunk(
        self, chunk: str, global_offset: int = 0
    ) -> List[int]:
        matches: List[int] = []
        m = len(self.pattern)
        i = 0

        while i < len(chunk):
            if chunk[i] == self.pattern[self.j]:
                i += 1
                self.j += 1
                if self.j == m:
                    matches.append(global_offset + i - m)
                    self.j = self.lps[self.j - 1]
            elif self.j != 0:
                self.j = self.lps[self.j - 1]
            else:
                i += 1
        return matches

    def reset(self) -> None:
        self.j = 0


def scan_log_stream(
    chunks: Generator[str, None, None], pattern: str
) -> Generator[int, None, None]:
    """Quét stream log, yield vị trí match."""
    scanner = StreamingKMP(pattern)
    offset = 0
    for chunk in chunks:
        for pos in scanner.process_chunk(chunk, offset):
            yield pos
        offset += len(chunk)

Java

import java.util.ArrayList;
import java.util.List;

public class StreamingKMP {
    private final String pattern;
    private final int[] lps;
    private int j = 0;

    public StreamingKMP(String pattern) {
        this.pattern = pattern;
        this.lps = buildLPS(pattern);
    }

    public List<Long> processChunk(String chunk, long globalOffset) {
        List<Long> matches = new ArrayList<>();
        int n = chunk.length(), m = pattern.length();

        for (int i = 0; i < n; ) {
            if (chunk.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == m) {
                    matches.add(globalOffset + i - m);
                    j = lps[j - 1];
                }
            } else if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return matches;
    }

    public void reset() { j = 0; }
}

Go

type StreamingKMP struct {
    pattern string
    lps     []int
    j       int
}

func NewStreamingKMP(pattern string) *StreamingKMP {
    return &StreamingKMP{
        pattern: pattern,
        lps:     buildLPS(pattern),
        j:       0,
    }
}

func (s *StreamingKMP) ProcessChunk(chunk string, globalOffset int) []int {
    var matches []int
    m := len(s.pattern)

    for i := 0; i < len(chunk); {
        if chunk[i] == s.pattern[s.j] {
            i++
            s.j++
            if s.j == m {
                matches = append(matches, globalOffset+i-m)
                s.j = s.lps[s.j-1]
            }
        } else if s.j != 0 {
            s.j = s.lps[s.j-1]
        } else {
            i++
        }
    }
    return matches
}

Phân tích:

• Streaming-safe: Con trỏ j giữ state giữa các chunk — pattern nằm vắt ngang hai chunk vẫn tìm được
• Memory O(m): Chỉ lưu LPS và state, không buffer toàn bộ text
• Deterministic O(n): Mỗi chunk xử lý tuyến tính, không phụ thuộc nội dung

Sai lầm điển hình

❌ Sai lầm 1: Reset j = 0 khi mismatch thay vì dùng LPS

Vấn đề: Nhiều người viết KMP nhưng vô tình biến thành brute-force.

# SAI: Reset j về 0 thay vì LPS[j-1]
if text[i] != pattern[j]:
    j = 0   # mất hết thông tin đã khớp!
    i += 1

Tại sao sai: Đây chính xác là naive search. Khi pattern có nhiều ký tự lặp (như DNA sequence AAAAT), mỗi mismatch phải quét lại từ đầu → quay về O(n × m).

# ĐÚNG: Fallback qua LPS
if text[i] != pattern[j]:
    if j != 0:
        j = lps[j - 1]  # nhảy về vị trí an toàn
    else:
        i += 1

❌ Sai lầm 2: Tăng i khi fallback trong LPS construction

Vấn đề: Trong vòng lặp xây LPS, tăng i ở nhánh fallback.

# SAI: tăng i trong nhánh fallback
while i < m:
    if pattern[i] == pattern[length]:
        length += 1
        lps[i] = length
        i += 1
    else:
        length = lps[length - 1]
        i += 1  # BUG! Bỏ qua vị trí cần kiểm tra

Tại sao sai: Khi fallback, ta cần kiểm tra lại pattern[i] với pattern[length] mới. Tăng i sẽ bỏ lỡ match tiềm năng, sinh ra LPS sai → tìm thiếu kết quả.

# ĐÚNG: KHÔNG tăng i khi fallback
while i < m:
    if pattern[i] == pattern[length]:
        length += 1
        lps[i] = length
        i += 1
    elif length != 0:
        length = lps[length - 1]
        # KHÔNG tăng i ở đây
    else:
        lps[i] = 0
        i += 1

❌ Sai lầm 3: Không xử lý overlapping matches

Vấn đề: Sau khi tìm thấy match, reset j = 0 thay vì j = LPS[j-1].

# SAI: bỏ qua overlapping matches
if j == m:
    result.append(i - j)
    j = 0  # mất khả năng tìm match chồng lấn

Tại sao sai: Với text "AAAA" và pattern "AA", kết quả đúng là [0, 1, 2] nhưng code trên chỉ tìm [0, 2].

# ĐÚNG: dùng LPS để tìm overlapping
if j == m:
    result.append(i - j)
    j = lps[j - 1]  # "AA" → LPS[1]=1 → tiếp tục từ j=1

Under the Hood

Chứng minh O(n + m)

Phương pháp amortized analysis sử dụng potential function Φ = j (giá trị con trỏ pattern):

Mỗi iteration của vòng while, một trong hai điều xảy ra:

1. Match:     i tăng 1, j tăng 1      → Φ tăng 1
2. Mismatch:
   a. j > 0:  j giảm (fallback LPS)   → Φ giảm ≥ 1, i giữ nguyên
   b. j = 0:  i tăng 1                → Φ giữ nguyên

Vì i chỉ tăng (tối đa n lần) và j ∈ [0, m]:
- Tổng số lần j tăng ≤ n (mỗi lần match, i và j cùng tăng)
- Tổng số lần j giảm ≤ tổng số lần j tăng ≤ n
- Vậy tổng iterations ≤ 2n

Xây LPS: tương tự, O(m)
Tổng: O(n + m)  ∎

KMP Automaton — góc nhìn lý thuyết automata

KMP thực chất xây dựng một Deterministic Finite Automaton (DFA) trên pattern:

Pattern: "ababc"    LPS: [0, 0, 1, 2, 0]

State transition diagram:

     a       b       a       b       c
(0) ───► (1) ───► (2) ───► (3) ───► (4) ───► [5] ACCEPT
 │        │        │        │        │
 │ ≠a     │ ≠b     │ ≠a     │ ≠b     │ ≠c
 ▼        ▼        ▼        ▼        ▼
(0)      (0)      (1)      (2)      (0)
          ↑ LPS[0] ↑ LPS[1] ↑ LPS[2] ↑ LPS[4]
              =0       =0       =1       =0

Mỗi state = số ký tự đã match
Failure link = LPS value → state to fallback to

So sánh hiệu năng thực tế

Thuật toán	Worst case	Best case	Cache behavior	Streaming
KMP	O(n + m) ✅	O(n + m)	Sequential scan ✅	✅ Giữ state
Boyer-Moore	O(n × m) ❌	O(n/m) 🚀	Right-to-left skip	❌ Cần random access
Rabin-Karp	O(n × m) ❌	O(n + m)	Hash computation	✅ Rolling
Naive	O(n × m) ❌	O(n)	Cache-friendly	❌ Backtrack

Khi nào KMP thắng tuyệt đối:

• Pattern có nhiều ký tự lặp (DNA: alphabet 4, binary data: alphabet 2)
• Streaming data — không thể random access text
• Cần worst-case guarantee (real-time systems, SLA-bound services)

Khi nào KMP thua:

• Alphabet lớn, pattern dài → Boyer-Moore thực tế nhanh hơn 3-5× nhờ skip lớn
• Cần tìm nhiều pattern → Aho-Corasick hoặc Rabin-Karp hiệu quả hơn

Trade-offs

Quyết định	KMP chọn	Đánh đổi
Worst-case guarantee	O(n + m) luôn	Thực tế chậm hơn Boyer-Moore trên text tiếng Anh
Preprocessing	O(m) cho LPS	Overhead không đáng kể trừ khi pattern thay đổi liên tục
Memory	O(m) cho LPS	Nhẹ hơn full DFA table O(m × Σ)
Streaming support	Native	Boyer-Moore không hỗ trợ

Checklist ghi nhớ

✅ Checklist triển khai

Xây dựng LPS

• [ ] LPS[0] luôn bằng 0 — proper prefix không tính chính chuỗi
• [ ] Khi mismatch trong LPS construction: fallback length = lps[length - 1], KHÔNG tăng i
• [ ] Kiểm tra LPS bằng tay với pattern có ký tự lặp trước khi tin kết quả

Thuật toán search

• [ ] Con trỏ i (text) chỉ tăng, không bao giờ giảm
• [ ] Mismatch khi j > 0: fallback j = lps[j - 1], KHÔNG tăng i
• [ ] Mismatch khi j = 0: tăng i
• [ ] Khi tìm thấy match: ghi nhận vị trí i - m, sau đó j = lps[j - 1] cho overlapping

Edge cases

• [ ] Pattern rỗng hoặc dài hơn text → return empty
• [ ] Pattern toàn ký tự giống nhau: "AAAA" → LPS = [0,1,2,3]
• [ ] Text và pattern giống hệt nhau → match tại vị trí 0
• [ ] Overlapping matches: "AA" trong "AAAA" → [0, 1, 2]

Production

• [ ] Streaming KMP: giữ state j giữa các chunk
• [ ] Validate input: null check, empty check trước khi xử lý
• [ ] Benchmark với worst-case input trước khi deploy

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

Bài 1: Tính LPS bằng tay — Foundation

Đề bài: Tính mảng LPS cho pattern "ABACABAB" và giải thích từng bước.

🧠 Quiz

Câu hỏi kiểm tra: Giá trị LPS[7] (vị trí cuối) của pattern "ABACABAB" là bao nhiêu?

• [ ] A. 1
• [x] B. 2
• [ ] C. 3
• [ ] D. 4 Giải thích: "ABACABAB" — proper prefix "AB" = suffix "AB" ✓. "ABA" ≠ "BAB" nên LPS[7] = 2. Lưu ý "ABAB" ≠ "ABAB" vì prefix và suffix chồng lấn quá mức.

💡 Gợi ý

• Xét từng vị trí từ 0 đến 7
• Tại mỗi vị trí, tìm prefix dài nhất cũng là suffix (proper)
• "ABAC" không có prefix = suffix nào

✅ Lời giải

Pattern:  A  B  A  C  A  B  A  B
Index:    0  1  2  3  4  5  6  7
LPS:      0  0  1  0  1  2  3  2

i=0: "A"         → 0
i=1: "AB"        → 0
i=2: "ABA"       → "A"="A" → 1
i=3: "ABAC"      → 0
i=4: "ABACA"     → "A"="A" → 1
i=5: "ABACAB"    → "AB"="AB" → 2
i=6: "ABACABA"   → "ABA"="ABA" → 3
i=7: "ABACABAB"  → "AB"="AB" → 2  (không phải 3 vì "ABA"≠"BAB")

Phân tích: O(m) = O(8) cho xây LPS. Điểm dễ sai: vị trí 7, nhiều người tưởng LPS tăng đều nhưng "ABAC" phá vỡ pattern.

Bài 2: KMP Search với Overlapping — Intermediate

Đề bài: Cho text "AABAABAAB" và pattern "AABAA". Tìm tất cả vị trí xuất hiện (bao gồm overlapping).

🧠 Quiz

Câu hỏi kiểm tra: Có bao nhiêu lần pattern xuất hiện trong text?

• [ ] A. 1
• [x] B. 2
• [ ] C. 3
• [ ] D. 0 Giải thích: Pattern "AABAA" xuất hiện tại vị trí 0 (AABAA|BAAB) và vị trí 3 (AAB|AABAA|B). Hai lần xuất hiện chồng lấn nhau.

💡 Gợi ý

• Tính LPS của "AABAA" trước: [0, 1, 0, 1, 2]
• Sau khi tìm thấy match đầu tiên, j = LPS[4] = 2
• Tiếp tục so sánh từ j = 2 (đã biết 2 ký tự đầu khớp)

✅ Lời giải

text = "AABAABAAB"
pattern = "AABAA"
# LPS: [0, 1, 0, 1, 2]

result = kmp_search(text, pattern)
print(result)  # [0, 3]

Phân tích: Time O(n + m) = O(9 + 5) = O(14). Overlapping match tại vị trí 3 được tìm nhờ j = LPS[4] = 2 — KMP biết "AA" cuối của match trước cũng là "AA" đầu của match tiếp.

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Complexity Analysis — phân tích Big-O, amortized analysis
• → Rabin-Karp — tiếp cận pattern matching bằng hashing
• Trie — Cây tiền tố — cấu trúc dữ liệu nền tảng cho Aho-Corasick
• Aho-Corasick — mở rộng failure function lên multi-pattern
• String Processing — Tổng quan — so sánh tổng hợp các thuật toán

Từ khóa glossary: KMP, Knuth-Morris-Pratt, failure function, prefix table, LPS array, pattern matching, string search

Tìm kiếm liên quan: thuật toán tìm chuỗi, tìm kiếm mẫu, xử lý chuỗi tuyến tính, bảng tiền tố