Deleng sumberé Algoritma panggolèkan string

'''Algoritma panggolèkan string''' utawa asring karan uga panyocokan string ya iku [[algoritma]] kanggo nggolèki kabèh kamunculan [[string]] cendhak <math>pattern[0..n-1]</math> sing karan pattern ing string sing luwih dawa <math>teks[0..m-1]</math> sing karan tèks.<ref>Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5</ref>

Panyocokkan string wujud pamasalahan paling prasaja saka kabèh pamasalahan string liyané, lan dianggep péranganing [[pamrosèsan data]], [[Kompresi data|pangomprèsian data]], [[analisis leksikal]], lan [[Sistem temu walik informasi|temu walik informasi]]. Tèknik kanggo ngrampungaké pamasalahan panyocokkan string racaké bakal ngasilaké implikasi langsung marang aplikasi string liyané<ref>Breslauer, Dany. 1992. Efficient String Algorithms. [http://citeseer.ist.psu.edu/breslauer92efficient.html dhokumèn]</ref>.

== Conto algoritma panyocokkan string ==

Algoritma-algoritma panyocokkan string bisa diklasifikasikaké dadi telung pérangan miturut arah panggolèkané.

Telung kategori iku ya iku:
* Saka arah sing paling alami, saka kiwa nengan, sing wujud arah kanggo maca, algoritma sing kalebu kategori iki ya iku:
*# [[#Algoritma brute force ing panggolèkan string|Algoritma Brute Force]]
*# Algoritma saka Morris lan Pratt, sing banjur dikembangaké déning [[Algoritma Knuth-Morris-Pratt|Knuth, Morris, lan Pratt]]
* Saka tengen ngiwa, arah sing racaké ngasilaké asil paling apik kanthi praktikal, contoné ya iku:
*# Algoritma saka [[Algoritma Boyer-Moore|Boyer lan Moore]], sing banjur akèh dikembangaké, dadi [[Algoritma turbo Boyer-Moore]], [[Algoritma tuned Boyer-Moore]], lan [[Algoritma Zhu-Takaoka]];
* Lan kategori pungkasan, saka arah sing ditemtokaké kanthi spesifik déning algoritma mau, arah iki ngasilaké asil paling apik kanthi téoritis, algoritma sing kalebu kategori iki ya iku:
*# [[Algoritma Colussi]]
*# [[Algoritma Crochemore-Perrin]]

== Algoritma brute force jroing panggolèkan string ==
Algoritma brute force wujud algoritma panyocokan string sing ditulis tanpa mikiraké paningkatan performa. Algoritma iki arang banget dienggo sajeroning praktèk, nanging migunani sajeroning studi pambandhing lan studi-studi liyané.

=== Carané kerja ===
Sacara sistematis, langkah-langkah sing dilakoni algoritma brute force nalika nyocokaké string ya iku:
# Algoritma brute force wiwit nyocokaké pattern ing awal tèks.
# Saka kiwa nengen, algoritma iki bakal nyocokaké karakter per karakter pattern karo karakter ing tèks sing padha selaras, nganti salah siji kondhisi iki kapenuhi:
## Karakter ing pattern lan ing tèks sing dibandhingaké ora cocog (mismatch).
## Kabèh karakter ing pattern cocog. Sawisé iku algoritma bakal nggenahi panemon ing posisi iki.
# Algoritma banjur terus nggèsèr pattern siji nengen, lan mbalèni langkah angka 2 nganti pattern ada ing ujung tèks.

Ing ngisor iki Algoritma brute force sing lagi temandang nggolèki string:

[[Gambar:Brute_Force_Dalam_Pencarian_String.jpg|Algoritma brute force sing lagi temandang nggolèki string.]]

=== Pseudocode ===
Pseudocode algoritma brute force iki:
 procedure BruteForceSearch(
        	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: integer 
 
 Algoritma:
         for (i:=0 to  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 
         endfor

== Réferènsi ==
{{reflist}}

== Pirsanana uga ==
* [[Pratélan algoritma]]
* [[Algoritma Knuth-Morris-Pratt]]
* [[Algoritma Boyer-Moore]]

== Pranala njaba ==
* [http://www-igm.univ-mlv.fr/~lecroq/string/ EXACT STRING MATCHING ALGORITHMS - Animation in Java]

{{DEFAULTSORT:Pencarian string}}
[[Kategori:Algoritma string]]
[[Kategori:Algoritma panggolèkan]]