Latihan 1: String Matching (KMP) — Algoritma

Latihan 1 dari materi String Matching (KMP) di Algoritma — praktek dengan editor kode interaktif, test case otomatis, dan hint terpandu. Langsung jalan di browser.

Lengkapi function buildLPS(pattern) supaya mengembalikan tabel LPS: array angka sepanjang pattern.length.

lps[i] adalah panjang awalan terpanjang yang juga jadi akhiran, untuk potongan pattern dari huruf 0 sampai huruf i. Seluruh potongan gak dihitung sebagai awalan (proper), jadi lps[0] selalu 0.

Contoh: "abab" jadi [0, 0, 1, 2], "aaaa" jadi [0, 1, 2, 3].

Kalau cocoknya putus, len mundur ke lps[len - 1], bukan langsung ke 0.

Empat console.log di bawahnya (yang menggabung hasil dengan koma) harus mencetak, berurutan:

0,0,1,2
0,1,2,3
0,0,0,1,2,3,0
0,1,0,1,2,3,4,5,2

Hint

lps[0] selalu 0. Untuk tiap huruf berikutnya, cek apakah awalan yang sedang cocok bisa bertambah satu huruf. Kalau gagal, coba awalan yang lebih pendek dulu, jangan langsung ke nol.
Pakai dua penunjuk: i untuk huruf yang dicek (mulai dari 1) dan len untuk panjang awalan yang cocok (mulai dari 0), dengan loop while (i < pattern.length). Kalau beda dan len > 0, len = lps[len - 1] tanpa memajukan i.
if (pattern[i] === pattern[len]) { len++; lps[i] = len; i++; } else if (len > 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; }

</> { } .css => #id fn()

Versi baru

HyperSheets

bagian dari BelajarWeb.dev

Membuka gerbang…

Latihan 1: String Matching (KMP) — Algoritma

Hint

Memperbarui Aplikasi