Algoritma pencarian string

Algoritma pencarian string (bahasa Inggris: string matching algorithm) atau sering disebut juga pencocokan string adalah algoritme untuk melakukan pencarian semua kemunculan string pendek  yang disebut pattern di string yang lebih panjang  yang disebut teks.Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5

Algoritma-algoritma pencocokkan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya.

 Dan kategori terakhir, dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoretis, algoritma yang termasuk kategori ini adalah:
 Algoritme Colussi
 Algoritme Crochemore-Perrin

salah satunya algoritma SUSAN

 Algoritma brute force dalam pencarian string 
Algoritma brute force (bahasa Inggris: brute-force search) merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktik, tetapi berguna dalam studi pembanding dan studi-studi lainnya.

 Cara kerja 
Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:
 Algoritma brute force 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 terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.

Berikut adalah Algoritma brute force yang sedang bekerja mencari string:

Algoritme brute force yang sedang bekerja mencari string.

 Pseudocode 
Pseudocode algoritma brute force ini:
 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

 Referensi 

 Lihat pula 
 Daftar algoritme
 Algoritme Knuth-Morris-Pratt
 Algoritme Boyer-Moore

 Pranala luar 
 EXACT STRING MATCHING ALGORITHMS - Animation in Java

Kategori:Algoritme string
Kategori:Algoritme pencarian