Brute-Force Search Pada Pencarian Kata Moe

Di Facebook saya mendapatkan sebuah status dari adik tingkat. Statusnya seperti ini

M E O E M M E O O M O M E E O O E M E O O M O M E M E M E M E O
E M E O E E M E O O M O M E M E O E O E M E M E M E O E O M O O
O M O M E E O O E M E M E M E O E M E O E M E M E O O O O M E M
M E O E O E O E M E O E M O M E E O E M E O E O M O E M O M M O
E M E O O M O M E M E M E M E O O M E M M E O O M O M E E O O E

cari kata 'MOE' secara vertikal atau horizontal
jika menyelesaikan < 1 menit, berarti IQ anda diatas rata2 *
jika menyelesaikan > 1 dan < 3 menit, berarti IQ anda rata2 **
jika menyelesaikan > 3 menit, berarti IQ anda dibawah rata2 ***

* dihitung berdasarkan feeling
** ga dihitung, kayanya pas aja
*** yang ini liat dari horoskop (bohong)

Secara komputasional ini bisa dipecahkan dengan menggunakan Brute Force Search

Brute-Force Search

Brute Force Search adalah metode pencarian dengan mengecek setiap kondisi yang ada pada kasus (Wikipedia, 2014. Hahaha). Dalam kasus ini kita mencari kata "MOE" pada matriks tersebut secara horizontal dan vertikal.

Sekarang kita coba analisis. Mari kita hilangkan spasi pada matriks tersebut.

MEOEMMEOOMOMEEOOEMEOOMOMEMEMEMEO
EMEOEEMEOOMOMEMEOEOEMEMEMEOEOMOO
OMOMEEOOEMEMEMEOEMEOEMEMEOOOOMEM
MEOEOEOEMEOEMOMEEOEMEOEOMOEMOMMO
EMEOOMOMEMEMEMEOOMEMMEOOMOMEEOOE

Matriks ini kita sebut sebagai matriks I. Dengan penyederhanaan ini dapat diketahui matriks tersebut berdimensi 5x33.

Iterasi yang dilakukan sepanjang matriks adalah dengan menggeser array berukuran 1x3 berisi kata "MOE" untuk dicek apakah terdapat urutan huruf yang secara berkesinambungan. Matriks pengecek tersebut adalah sebagai berikut:

MOE

Matriks tersebut kita sebut sebagai matrik K.

Karena yang kita cari adalah 3 huruf dan pencarian dilakukan dengan bergeser mencari 3 huruf di setiap elemen maka jika (M, N) adalah dimensi matriks I dan (m,n) adalah dimensi matriks K dan karena pencarian baik secara horizontal maupun vertikal menggunakan banyak huruf maka  pencarian dilakukan sebanyak ((M-(m*n))+1) + ((N-(m*n))+1).

Program dari pencarian ini adalah sebagai berikut:

#include <iostream>

int main(){

 int baris = 5;
 int kolom = 33;

 //inisialisasi matriks kasus
 char huruf[baris][kolom];
 strcpy(huruf[0],"MEOEMMEOOMOMEEOOEMEOOMOMEMEMEMEO");
 strcpy(huruf[1],"EMEOEEMEOOMOMEMEOEOEMEMEMEOEOMOO");
 strcpy(huruf[2],"OMOMEEOOEMEMEMEOEMEOEMEMEOOOOMEM");
 strcpy(huruf[3],"MEOEOEOEMEOEMOMEEOEMEOEOMOEMOMMO");
 strcpy(huruf[4],"EMEOOMOMEMEMEMEOOMEMMEOOMOMEEOOE");

 char kata[3];
 strcpy(kata,"MOE");

 int kolomKata = 3;

 int banyakKata = 0; 

 int i,j, ii;
 bool benar = false;

 
 // bergerak di sepanjang elemen
 for (i = 0; i < baris; i++){
  for (j = 0; j < kolom ; j++) {
   
   //pencarian horizontal   
   if (j < kolom - (kolomKata) + 1){
    benar = true;   
    ii = 0;
    while (ii < kolomKata && benar) {
     if (!benar || ! (huruf[i][j+ii] == kata[ii]) )  {
      benar = false;
     }else{
      ii++; 
     }
    }

    if (benar) {
     banyakKata++;
    }
   }
   


   //pencarian vertikal

   if (i < baris - kolomKata + 1){
    benar = true;   
    ii = 0;
    while (ii < kolomKata && benar) {
     if (!benar || ! (huruf[i+ii][j] == kata[ii]) )  {
      benar = false;
     }else{
      ii++; 
     }
    }

    if (benar) {
     banyakKata++;
    }
   }
  }

 }

 printf("Banyak kata %s adalah %d\n", kata, banyakKata);

 return 0;
}

dari program tersebut didapat hasil sebagai berikut

Banyak kata MOE adalah 3

Demikian tentang Brute-Force Search kali ini. Terima kasih! *peace*