Penjelasan pencarian string KMP: cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan KMP

Pencarian string menanyakan di mana sebuah pattern pendek muncul dalam teks yang lebih panjang. Metode naif mencoba setiap posisi awal dan membandingkan karakter satu per satu. Pada teks biasa cara ini cepat, tetapi pada input yang repetitif lambat: mencari aaaab di dalam aaaaaaaaaa membandingkan hampir seluruh pattern di setiap posisi, sehingga waktunya O(n × m).

KMP tidak pernah membaca ulang karakter teks setelah ketidakcocokan. Donald Knuth, James H. Morris, dan Vaughan Pratt menerbitkannya pada 1977 dalam "Fast Pattern Matching in Strings".

Ide dasar dengan kata-kata sederhana

Misalkan Anda mencari pattern ABABC, sudah cocok ABAB, dan karakter teks berikutnya bukan C. Bagian yang baru cocok, ABAB, berakhir dengan AB, yang juga merupakan awal pattern. Jadi Anda sudah tahu percobaan berikutnya dimulai dengan 2 karakter yang cocok, dan Anda dapat melanjutkan perbandingan dari posisi pattern 2 alih-alih mulai dari awal.

Prefix function menyimpan angka-angka ini. pi[i] adalah panjang proper prefix terpanjang dari pattern[0..i] yang juga merupakan suffix-nya (proper berarti bukan seluruh string).

Misalnya, pi[4] = 3 karena ABABA diawali dan diakhiri dengan ABA. pi[5] = 0 karena tidak ada prefix dari ABABAC yang berakhir dengan C.

Contoh langkah demi langkah

Cari pattern ABABC (prefix function 0, 0, 1, 2, 0) dalam teks ABABABC. Variabel k menghitung berapa karakter pattern yang sedang cocok.

Penunjuk teks maju 7 kali dan tidak pernah mundur. Metode naif akan mengulang dari posisi 1 dan membandingkan sebagian karakter lagi.

Implementasi Python

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    """Return the start index of every occurrence (overlaps included)."""
    if not pattern:
        return []
    pi, k, hits = prefix_function(pattern), 0, []
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - k + 1)
            k = pi[k - 1]          # keep going to find overlapping matches
    return hits

print(prefix_function("ABABACA"))      # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC"))  # [2]
print(kmp_search("AAAAA", "AA"))       # [0, 1, 2, 3]

Kompleksitas waktu dan ruang

Algoritma naif O(n × m) pada kasus terburuk tetapi sering mendekati O(n) pada teks bahasa alami, sehingga keunggulan KMP terutama terlihat pada data yang repetitif.

Varian dan kesalahan umum

• Off-by-one pada fallback: setelah ketidakcocokan, set k = pi[k - 1], bukan pi[k]. pi diindeks dengan posisi cocok terakhir.
• Memakai if alih-alih while untuk fallback: Anda mungkin perlu beberapa fallback berturut-turut sebelum sebuah karakter cocok.
• Lupa mereset k setelah kecocokan penuh: set k = pi[k - 1] untuk menemukan kecocokan yang tumpang tindih, atau k = 0 untuk yang tidak tumpang tindih.
• Trik penyambungan: hitung prefix function dari pattern + separator + text, dengan separator yang tidak muncul di keduanya; setiap posisi yang nilainya sama dengan m adalah akhir sebuah kecocokan.
• Z-algorithm menghitung array yang sangat mirip dan juga mencari dalam O(n + m).

Kapan memakainya dan penggunaannya di dunia nyata

• Soal wawancara: implementasi strStr(), shortest palindrome (prefix function dari s + "#" + reversed(s)), repeated substring pattern, periode terkecil string (m - pi[m - 1]).
• Dunia nyata: pencarian pada sekuens DNA dan aliran paket jaringan, ketika waktu linear pada kasus terburuk penting.