StringMenengahFase D–FE1E5

KMP Search

KMP mencari pola di dalam teks tanpa pernah mengecek ulang huruf yang sudah cocok. Rahasianya adalah tabel LPS (awalan yang sekaligus akhiran) yang dihitung dari pola: saat terjadi ketidakcocokan, pola digeser jauh sesuai LPS, bukan hanya satu langkah seperti cara naif. Alhasil pencarian jauh lebih cepat pada teks panjang. Visualisasi menggeser pola dan menunjukkan lompatan yang dilewati.

Contoh kasus

Fitur Ctrl+F di editor kode dan peramban, serta mesin pencari yang menemukan kata di dalam dokumen panjang secara instan.

Silabus

Saat tak cocok, geser pola sesuai tabel LPS (bukan +1) — huruf yang sudah cocok tak pernah dicek ulang.

Tujuan Belajar

·Memahami kelemahan pencarian naif (banyak cek ulang)
·Menjelaskan tabel LPS (awalan = akhiran)
·Melihat bagaimana KMP melompat saat mismatch

Cara Kerja

·Hitung dulu tabel LPS dari pola (panjang awalan yang juga menjadi akhiran).
·Cocokkan pola dengan teks huruf demi huruf.
·Bila cocok, kedua penunjuk maju bersama.
·Bila TAK cocok, geser pola sesuai LPS — penunjuk teks tetap, tak ada cek ulang.

Prasyarat

·String dan indeks
·Konsep awalan (prefix) dan akhiran (suffix)

Contoh Nyata

·Ctrl+F di editor kode dan peramban.
·Pencarian kata di dokumen panjang.
·Penyaringan teks dan deteksi pola di lalu lintas jaringan.

Kompleksitas O(panjang teks + panjang pola)