Algoritma Brute Force

Hai ~
Ketemu lagi nih . Setelah kemarin kemarin kita membahas tentang algoritma sorting dan searching, kali ini kita akan membahas tentang algoritma pencocokan string . Algoritma brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktik, namun berguna dalam studi pembanding dan studi-studi lainnya.

Bagaimana cara kerja dari algoritma ini ? Nah disimak yah~

Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:

1. Algoritma brute force mulai mencocokkan pattern pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
   1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
   2. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
3. 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:

Berikut adalah pseucode dari algoritma brute force

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

Dan ini contoh implementasi pada java :

public class StringMatch {

   private static void match(char[] text, char[] pattern) {

     int j;

     int cek = 0;

     for (int i = 0; i <= text.length - pattern.length; i++) {

        j= 0;

        while (j < pattern.length && text[i + j] == pattern[j]){

           j++;

        }

        if (j >= pattern.length) {

           cek++;

        }

     }

     if (cek > 0) {

        System.out.println("DATA COCOK");

     } else {

        System.out.println("DATA TIDAK COCOK");

     }

   }

   public static void main(String[] args) {

      char[]

x = {'I', 'C', 'O', 'M'};

      char[]

y = {'I', 'C', 'O', 'M', 'I', 'T', '.', 'C', 'O', 'M'};

      match(y,x);

   }

}