Chương 35 - KMP (Knuth–Morris–Pratt)

KMP giải bài substring matching trong O(n + m), cốt lõi là mảng LPS (Longest Prefix Suffix) - với mỗi vị trí i trong pattern, lps[i] = độ dài prefix dài nhất của pattern[0..i] đồng thời là suffix của nó (không phải chính nó).

LPS - visualize bằng ví dụ ababaca

LPS là khái niệm khó nhất KMP. Trace tay với pattern = "ababaca":

index  :   0    1    2    3    4    5    6
char   :   a    b    a    b    a    c    a
LPS    :   0    0    1    2    3    0    1

Giải thích từng ô:
  LPS[0]=0  (1 ký tự, không có proper prefix nào)
  LPS[1]=0  "ab" - prefix "a" ≠ suffix "b"
  LPS[2]=1  "aba" - prefix "a" = suffix "a" → 1
  LPS[3]=2  "abab" - prefix "ab" = suffix "ab" → 2
  LPS[4]=3  "ababa" - prefix "aba" = suffix "aba" → 3
  LPS[5]=0  "ababac" - không có prefix "_" = suffix "_c" → 0
  LPS[6]=1  "ababaca" - prefix "a" = suffix "a" → 1

Trực giác: LPS[i] cho biết khi mismatch tại pattern[i+1], ta không cần restart từ đầu - có thể nhảy về pattern[LPS[i]] vì các ký tự pattern[0..LPS[i]-1] chắc chắn đã match (do nó cũng là suffix của những gì đã match).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • LPS array: lps[i] = longest proper prefix = suffix của pattern[0..i].
  • Mỗi ký tự pattern bị compare tối đa 2 lần → O(n + m).
  • Sentinel # cần KHÔNG xuất hiện trong input (chọn ký tự an toàn).
  • Trick: len(s) - lps[-1] chia hết len(s) ↔︎ s là string lặp.

Khi nào dùng pattern này?

  • Substring matching, đặc biệt khi pattern xuất hiện nhiều.
  • Bài “longest happy prefix”, “shortest palindrome”, “repeated pattern”.
  • Khi không thể chấp nhận collision risk của rolling hash.

Template code 

def build_lps(p: str) -> list[int]:
    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 > 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps


def kmp_search(text: str, p: str) -> list[int]:
    lps = build_lps(p)
    result = []
    i = j = 0
    while i < len(text):
        if text[i] == p[j]:
            i += 1; j += 1
            if j == len(p):
                result.append(i - j)
                j = lps[j - 1]
        elif j > 0:
            j = lps[j - 1]
        else:
            i += 1
    return result

Bài tự luyện cuối chương

  • LC 686 - Repeated String Match
  • LC 1392 - Longest Happy Prefix
  • LC 3008 - Find Beautiful Indices

35.1 Implement strStr() (LC 28)

Đề bài

Tìm index đầu tiên của needle trong haystack, hoặc -1.

Ví dụ 

Input:  haystack="sadbutsad", needle="sad"
Output: 0

Ràng buộc

  • 1 <= len(haystack), len(needle) <= 10^4
  • haystack, needle chỉ chứa chữ thường

Clarifying questions

  • needle rỗng? → Trả 0.
  • haystack rỗng? → Trả -1 (trừ khi needle rỗng).

Hướng tiếp cận

KMP O(n + m) time, O(m) space cho lps.

Code Python 3 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m == 0: return 0
        lps = [0] * m
        length = 0
        i = 1
        while i < m:
            if needle[i] == needle[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length > 0:
                length = lps[length - 1]
            else:
                i += 1

        i = j = 0
        while i < n:
            if haystack[i] == needle[j]:
                i += 1; j += 1
                if j == m:
                    return i - j
            elif j > 0:
                j = lps[j - 1]
            else:
                i += 1
        return -1

Phân tích độ phức tạp

  • Thời gian: O(n + m).
  • Bộ nhớ: O(m) cho LPS.

Bình luận

  • Brute force O(n·m) vẫn pass với m, n ≤ 10⁴ trên LC, nhưng KMP là lời giải tối ưu hơn về mặt thuật toán và thể hiện được khả năng nắm pattern matching tuyến tính.

Bài tự luyện liên quan

  • LC 214 - Shortest Palindrome (bài 35.2)
  • LC 459 - Repeated Substring Pattern (bài 35.3)

35.2 Shortest Palindrome (LC 214) - KMP version

Đề bài

Như Chương 34.4 nhưng dùng KMP.

Ví dụ 

Input:  s = "aacecaaa"
Output: "aaacecaaa"   (thêm ký tự ÍT NHẤT vào ĐẦU s để thành palindrome)

Ràng buộc

  • 0 <= len(s) <= 5·10^4

Clarifying questions

  • s đã palindrome? → Trả s.
  • s rỗng? → Trả s.

Hướng tiếp cận

Tạo combined = s + '#' + reverse(s). Tính lps của combined; giá trị lps[-1] chính là độ dài prefix dài nhất của s đồng thời là suffix của reverse(s) = prefix palindrome dài nhất.

Code Python 3 

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        combined = s + '#' + s[::-1]
        lps = [0] * len(combined)
        length = 0
        for i in range(1, len(combined)):
            while length > 0 and combined[i] != combined[length]:
                length = lps[length - 1]
            if combined[i] == combined[length]:
                length += 1
            lps[i] = length
        return s[lps[-1]:][::-1] + s

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n).

Bình luận

  • Trick # tránh prefix overlap suffix vô tình (palindrome ảo).

Bài tự luyện liên quan

  • LC 1392 - Longest Happy Prefix (bài 35.6)
  • LC 5 - Longest Palindromic Substring

35.3 Repeated Substring Pattern (LC 459)

Đề bài

Kiểm tra s có thể tạo bằng concat nhiều lần 1 substring không.

Ví dụ 

Input:  s = "abab"
Output: True
("abab" = "ab" lặp 2 lần ⇒ True)

Ràng buộc

  • 1 <= len(s) <= 10^4
  • s chỉ chứa chữ thường

Clarifying questions

  • s chỉ 1 ký tự? → Trả False (cần ≥ 2 lần lặp).

Hướng tiếp cận

Trick KMP: nếu s = pattern * k (k ≥ 2), thì lps[-1] > 0 và n - lps[-1] chia hết n.

Cụ thể: len(pattern) = n - lps[-1].

Code Python 3 

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        lps = [0] * n
        length = 0
        for i in range(1, n):
            while length > 0 and s[i] != s[length]:
                length = lps[length - 1]
            if s[i] == s[length]:
                length += 1
            lps[i] = length
        return lps[-1] > 0 and n % (n - lps[-1]) == 0

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n).

Bình luận

  • One-liner trick: (s + s)[1:-1].find(s) != -1. Tinh tế nhưng less efficient.

Bài tự luyện liên quan

  • LC 28 - strStr() (bài 35.1)
  • LC 1392 - Longest Happy Prefix (bài 35.6)

35.4 Find All Anagrams in a String (LC 438)

Đề bài

Tìm tất cả start index trong s mà substring length-|p| là anagram của p.

Ví dụ 

Input:  s="cbaebabacd", p="abc"
Output: [0, 6]

Ràng buộc

  • 1 <= len(s), len(p) <= 3·10^4

Clarifying questions

  • p > s? → Trả [].
  • Anagram phải sort? → Không, dùng Counter equality.

Hướng tiếp cận

Sliding window + Counter. KMP không trực tiếp giải bài này - Anagram không phải substring match. Nhưng vẫn được liệt kê vì nằm trong family bài “string pattern”.

Code Python 3 

from collections import Counter
from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p): return []
        need = Counter(p)
        have = Counter(s[:len(p)])
        result = []
        if have == need:
            result.append(0)
        for i in range(len(p), len(s)):
            have[s[i]] += 1
            have[s[i - len(p)]] -= 1
            if have[s[i - len(p)]] == 0:
                del have[s[i - len(p)]]
            if have == need:
                result.append(i - len(p) + 1)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n + m · k) với k = bảng chữ; thường O(n).
  • Bộ nhớ: O(k).

Bình luận

  • Bẫy: so sánh Counter mỗi vòng → O(26) không phải O(1); vẫn ổn cho LC.
  • Follow-up: LC 30 (Substring with Concatenation) tổng quát hơn.

Bài tự luyện liên quan

  • LC 567 - Permutation in String
  • LC 30 - Substring with Concatenation of All Words

35.5 Maximum Number of Occurrences of a Substring (LC 1297)

Đề bài

Cho s, maxLetters, minSize, maxSize. Tìm substring có maxOccurrence mà length ∈ [minSize, maxSize] và số ký tự phân biệt ≤ maxLetters.

Ví dụ 

Input:  s="aababcaab", maxLetters=2, minSize=3, maxSize=4
Output: 2

Ràng buộc

  • 1 <= len(s) <= 10^5
  • 1 <= maxLetters <= 26

Clarifying questions

  • maxLetters > 26? → Cho phép mọi substring length-minSize.
  • maxSize không dùng? → Đúng - chỉ minSize matter.

Hướng tiếp cận

Trick: chỉ cần xét length = minSize (substring lớn hơn không thể xuất hiện nhiều hơn).

Sliding window + Counter.

Code Python 3 

from collections import Counter, defaultdict

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        freq: dict[str, int] = defaultdict(int)
        for i in range(len(s) - minSize + 1):
            sub = s[i:i + minSize]
            if len(set(sub)) <= maxLetters:
                freq[sub] += 1
        return max(freq.values(), default=0)

Phân tích độ phức tạp

  • Thời gian: O(n · minSize).
  • Bộ nhớ: O(n).

Bình luận

  • Insight minSize only: nếu substring length-L xuất hiện k lần thì substring length-(L-1) cũng xuất hiện ≥ k lần (mỗi cái → prefix length-(L-1)).

Bài tự luyện liên quan

  • LC 187 - Repeated DNA Sequences
  • LC 30 - Substring with Concatenation of All Words

35.6 Longest Happy Prefix (LC 1392)

Đề bài

“Happy prefix” = prefix non-trivial đồng thời là suffix. Trả về cái dài nhất.

Ví dụ 

Input:  s = "level"
Output: "l"   (prefix DÀI NHẤT của s cũng là suffix của s, KHÔNG bằng chính s;
              empty string nếu không tồn tại)

Ràng buộc

  • 1 <= len(s) <= 10^5
  • s chỉ chứa chữ thường

Clarifying questions

  • s không có happy prefix? → Trả ““.

Hướng tiếp cận

Trực tiếp lps[-1] của s chính là đáp án.

Code Python 3 

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        lps = [0] * n
        length = 0
        for i in range(1, n):
            while length > 0 and s[i] != s[length]:
                length = lps[length - 1]
            if s[i] == s[length]:
                length += 1
            lps[i] = length
        return s[:lps[-1]]

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n).

Bình luận

  • Bẫy: trả s[:lps[-1]] - vẫn còn case rỗng nếu không có happy prefix.
  • Follow-up: LC 459 (Repeated Substring Pattern) - cùng LPS.

Bài tự luyện liên quan

  • LC 28 - strStr().

Tóm tắt chương & Quyết định

LPS trace - ababaca

i char j (prev LPS) lps[i]
0 a – 0
1 b lps[0]=0; s[0]!=s[1] 0
2 a j=0; s[0]==s[2] ⇒ j=1 1
3 b j=1; s[1]==s[3] ⇒ j=2 2
4 a j=2; s[2]==s[4] ⇒ j=3 3
5 c j=3; s[3]!=s[5]; fallback j=lps[2]=1; s[1]!=s[5]; fallback j=lps[0]=0; s[0]!=s[5] 0
6 a j=0; s[0]==s[6] ⇒ j=1 1

⇒ lps = [0, 0, 1, 2, 3, 0, 1].

Sentinel safety

Khi concat P + '#' + T (LC tham khảo), # phải không nằm trong charset cho phép. Nếu input có thể chứa mọi ký tự Unicode, dùng cặp 2 sentinel hoặc Z-function (Chương 36) trực tiếp.

Find All Anagrams (LC 438) ≠ KMP

  • Bài này là sliding window + counter. Đặt ở chương này chỉ để so sánh với “pattern matching theo cấu trúc”.
  • KMP matching liên tục theo thứ tự; anagram matching không quan tâm thứ tự ký tự.

KMP vs Z (Chương 36)

  KMP Z
Preprocess LPS array của P Z array của P + '#' + T
Tư duy “Failure → quay lui khôn ngoan” “Khớp tiền tố tại mọi vị trí”
Cài đặt Failure function, 2 con trỏ 1 box [l, r), dễ off-by-one
Ứng dụng đặc thù Period of string, find pattern LCP, distinct substring, Z-array properties