StringsMenengahFase D–FE1E5
KMP String Matching
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.
Example use case
Fitur Ctrl+F di editor kode dan peramban, serta mesin pencari yang menemukan kata di dalam dokumen panjang secara instan.
Syllabus
Saat tak cocok, geser pola sesuai tabel LPS (bukan +1) — huruf yang sudah cocok tak pernah dicek ulang.
Objectives
- ·Memahami kelemahan pencarian naif (banyak cek ulang)
- ·Menjelaskan tabel LPS (awalan = akhiran)
- ·Melihat bagaimana KMP melompat saat mismatch
How It Works
- ·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.
Prerequisites
- ·String dan indeks
- ·Konsep awalan (prefix) dan akhiran (suffix)
Real-World Uses
- ·Ctrl+F di editor kode dan peramban.
- ·Pencarian kata di dokumen panjang.
- ·Penyaringan teks dan deteksi pola di lalu lintas jaringan.
Complexity O(panjang teks + panjang pola)