Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T10:28:57Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 10.28
Baris 1:		Baris 1:
	'''Algoritma Knuth-Morris-Pratt''' adalah salah satu [[algoritme pencarian string]], dikembangkan secara terpisah oleh [[Donald Knuth\|Donald E. Knuth]] pada tahun 1967 dan [[James Morris\|James H. Morris]] bersama [[Vaughan Pratt\|Vaughan R. Pratt]] pada tahun 1966, tetapi keduanya memublikasikannya secara bersamaan pada tahun 1977.		'''Algoritma Knuth-Morris-Pratt''' adalah salah satu [[algoritme pencarian string]], dikembangkan secara terpisah oleh [[Donald Knuth\|Donald E. Knuth]] pada tahun 1967 dan [[James Morris\|James H. Morris]] bersama [[Vaughan Pratt\|Vaughan R. Pratt]] pada tahun 1966, tetapi keduanya memublikasikannya secara bersamaan pada tahun 1977.

	Jika kita melihat [[Algoritme pencarian string#Algoritme brute force dalam pencarian string\|algoritme brute force]] lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.		Jika kita melihat [[Algoritme pencarian string#Algoritme brute force dalam pencarian string\|algoritme brute force]] lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.<ref>Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5</ref>

	== Cara kerja ==		== Cara kerja ==
	Perhitungan penggeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan <math>teks[i..i+n-1]</math>, kita bisa menganggap ketidakcocokan pertama terjadi di antara <math>teks[i+j]</math> dan <math>pattern[j]</math>, dengan <math>0 < j < n</math>. Berarti, <math>teks[i..i+j-1] = pattern[0..j-1]</math> dan <math>a=teks[i+j]</math> tidak sama dengan <math>b=pattern[j]</math>. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan <math>v</math> dari pattern akan sama dengan sebagian akhiran <math>u</math> dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan <math>v</math> tersebut sejajar dengan akhiran dari <math>u</math>.		Perhitungan penggeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan <math>teks[i..i+n-1]</math>, kita bisa menganggap ketidakcocokan pertama terjadi di antara <math>teks[i+j]</math> dan <math>pattern[j]</math>, dengan <math>0 < j < n</math>. Berarti, <math>teks[i..i+j-1] = pattern[0..j-1]</math> dan <math>a=teks[i+j]</math> tidak sama dengan <math>b=pattern[j]</math>. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan <math>v</math> dari pattern akan sama dengan sebagian akhiran <math>u</math> dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan <math>v</math> tersebut sejajar dengan akhiran dari <math>u</math>.

	Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokkan di karakter ke-<math>j</math> dari pattern. Tabel itu harus memuat <math>next[j]</math> yang merupakan posisi karakter <math>pattern[j]</math> setelah digeser, sehingga kita bisa menggeser pattern sebesar <math>j-next[j]</math> relatif terhadap teks.		Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokkan di karakter ke-<math>j</math> dari pattern. Tabel itu harus memuat <math>next[j]</math> yang merupakan posisi karakter <math>pattern[j]</math> setelah digeser, sehingga kita bisa menggeser pattern sebesar <math>j-next[j]</math> relatif terhadap teks.<ref>Knuth, Donald E. Morris, James H. Pratt, Vaughan R. 1977. Fast Pattern Matching in Strings, SIAM Journal of Computing Vol 6 No.2.</ref>

	Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string:		Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string:
Baris 49:		Baris 49:

	Deklarasi:		Deklarasi:
	i, j,next: integer		i, j,next: integer
	kmpNext: array[0..n] of interger		kmpNext: array[0..n] of interger

	Algoritma:		Algoritma:
	preKMP(n, P, kmpNext)		preKMP(n, P, kmpNext)
	i:=0		i:=0
	while (i<= m-n) do		while (i<= m-n) do
	j:=0		j:=0
	while (j < n and T[i+j] = P[j]) do		while (j < n and T[i+j] = P[j]) do
	j:=j+1		j:=j+1
	endwhile		endwhile
Baris 69:		Baris 69:
	== Kompleksitas ==		== Kompleksitas ==
	Algoritma ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritma ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alpabet		Algoritma ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritma ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alpabet

	~~== Referensi ==~~


	== Lihat pula ==		== Lihat pula ==
Baris 81:		Baris 78:
	* [http://www-igm.univ-mlv.fr/~lecroq/string/node8.html Halaman berisi penjelasan tentang algoritma Knuth-Morris-Pratt dan juga sebuah applet yang menganimasikan cara kerjanya]		* [http://www-igm.univ-mlv.fr/~lecroq/string/node8.html Halaman berisi penjelasan tentang algoritma Knuth-Morris-Pratt dan juga sebuah applet yang menganimasikan cara kerjanya]

			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Knuth-Morris-Pratt&oldid=29188057 Wikipedia bahasa Indonesia], revisi 29188057 (2026-05-02T15:40:56Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Knuth-Morris-Pratt&oldid=29188057 Wikipedia bahasa Indonesia], revisi 29188057 (2026-05-02T15:40:56Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29188057; atribusi sumber disertakan.

2026-08-23T10:00:17Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29188057; atribusi sumber disertakan.

Halaman baru

'''Algoritma Knuth-Morris-Pratt''' adalah salah satu [[algoritme pencarian string]], dikembangkan secara terpisah oleh [[Donald Knuth|Donald E. Knuth]] pada tahun 1967 dan [[James Morris|James H. Morris]] bersama [[Vaughan Pratt|Vaughan R. Pratt]] pada tahun 1966, tetapi keduanya memublikasikannya secara bersamaan pada tahun 1977.

Jika kita melihat [[Algoritme pencarian string#Algoritme brute force dalam pencarian string|algoritme brute force]] lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.

== Cara kerja ==
Perhitungan penggeseran pada algoritma ini adalah sebagai berikut, bila terjadi ketidakcocokkan pada saat pattern sejajar dengan <math>teks[i..i+n-1]</math>, kita bisa menganggap ketidakcocokan pertama terjadi di antara <math>teks[i+j]</math> dan <math>pattern[j]</math>, dengan <math>0 < j < n</math>. Berarti, <math>teks[i..i+j-1] = pattern[0..j-1]</math> dan <math>a=teks[i+j]</math> tidak sama dengan <math>b=pattern[j]</math>. Ketika kita menggeser, sangat beralasan bila ada sebuah awalan <math>v</math> dari pattern akan sama dengan sebagian akhiran <math>u</math> dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan <math>v</math> tersebut sejajar dengan akhiran dari <math>u</math>.

Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser seandainya terdeteksi ketidakcocokkan di karakter ke-<math>j</math> dari pattern. Tabel itu harus memuat <math>next[j]</math> yang merupakan posisi karakter <math>pattern[j]</math> setelah digeser, sehingga kita bisa menggeser pattern sebesar <math>j-next[j]</math> relatif terhadap teks.

Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mencocokkan string:
# Algoritma Knuth-Morris-Pratt mulai mencocokkan pattern pada awal teks.
# Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
## Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
## Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
# Algoritma kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

== Pseudocode ==
Berikut adalah pseudocode algoritma KMP pada fase pra-pencarian:
procedure preKMP(
input P: array[0..n-1] of char,
input n: integer,
input/output kmpNext: array[0..n] of integer
)
Deklarasi:
i,j: integer

Algoritma
i:= 0;
j:= kmpNext[0]:= -1;
while (i < n) {
while (j > -1 and not(P[i] = P[j]))
j:= kmpNext[j];
i:= i+1;
j:= j+1;
if (P[i] = P[j])
kmpNext[i]:= kmpNext[j];
else
kmpNext[i]:= j;
endif
endwhile

Dan berikut adalah pseudocode algoritma KMP pada fase pencarian:
procedure KMPSearch(
input m, n: integer,
input P: array[0..n-1] of char,
input T: array[0..m-1] of char,
output ketemu: array[0..m-1] of boolean
)

Deklarasi:
i, j,next: integer
kmpNext: array[0..n] of interger

Algoritma:
preKMP(n, P, kmpNext)
i:=0
while (i<= m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n) then
ketemu[i]:=true;
endif
next:= j - kmpNext[j]
i:= i+next
endwhile

== Kompleksitas ==
Algoritma ini menemukan semua kemunculan dari pattern dengan panjang n di dalam teks dengan panjang m dengan kompleksitas waktu O(m+n). Algoritma ini hanya membutuhkan O(n) ruang dari memory internal jika teks dibaca dari file eksternal. Semua besaran O tersebut tidak tergantung pada besarnya ruang alpabet

== Referensi ==

== Lihat pula ==
* [[Daftar algoritme]]
* [[Algoritme pencarian string]]
* [[Algoritme Boyer-Moore]]

== Pranala luar ==
* [http://www-igm.univ-mlv.fr/~lecroq/string/node8.html Halaman berisi penjelasan tentang algoritma Knuth-Morris-Pratt dan juga sebuah applet yang menganimasikan cara kerjanya]

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Knuth-Morris-Pratt&oldid=29188057 Wikipedia bahasa Indonesia], revisi 29188057 (2026-05-02T15:40:56Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Algoritma Knuth-Morris-Pratt - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29188057; atribusi sumber disertakan.