Algoritma KMP (Knuth–Morris–Pratt)

Algoritma KMP (Knuth–Morris–Pratt) adalah salah satu algoritma yang dapat digunakan untuk mencari dimana sebuah string (dalam kasus ini dinamakan sebagai pola) apakah ditemukan di dalam kumpulan string lain dengan ukuran yang lebih besar. Contoh yang dibahas kali ini adalah mengenai pencarian kata dari sebuah input teks.
Knuth–Morris–Pratt menggunakan pendekatan pengamatan bahwa ketika sebuah ketidakcocokan terjadi, data input tersebut akan mengambil informasi tertentu untuk menentukan dimanakah selanjutnya pencarian dilakukan, dengan demikian pengecekan dapat dilakukan secara tidak berurutan tetapi tetap akan melewati pengecekan string yang sudah dicek sebelumnya.

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan teks yang digunakan sebagai input
Diasumsikan data input adalah sebagai berikut:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

2. Tentukan pola kata kunci yang digunakan dalam pencarian
Diasumsikan pola adalah sebagai berikut
labor

3. Lakukan pencarian kata kunci menggunakan algoritma ini

Dim idxKata() As Integer = CariPola(input, pola)

* Gunakan fungsi ini untuk mencari pola pada data input

Public Function CariPola(input As String, pola As String) As Integer()
	Dim hasil As New List(Of Integer)()
	Dim M As Integer = pola.Length
	Dim N As Integer = input.Length
	Dim j As Integer = 0
	Dim lps As Integer() = New Integer(M - 1) {}
	lps(0) = 0

	Dim panjangPola As Integer = 0
	Dim i As Integer = 1
	While i < M
		If pola(i) = pola(panjangPola) Then
			panjangPola += 1
			lps(i) = panjangPola
			i += 1
		Else
			If panjangPola <> 0 Then
				panjangPola = lps(panjangPola - 1)
			Else
				lps(i) = 0
				i += 1
			End If
		End If
	End While

	i = 0
	While i < N
		If pola(j) = input(i) Then
			j += 1
			i += 1
		End If

		If j = M Then
			hasil.Add(i - j)
			j = lps(j - 1)

		ElseIf i < N AndAlso pola(j) <> input(i) Then
			If j <> 0 Then
				j = lps(j - 1)
			Else
				i = i + 1
			End If
		End If
	End While

	Return hasil.ToArray()
End Function

Hasil akhir adalah: (klik untuk perbesar gambar)

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.