String Matching - Using Brute Force and Horspool Algorithm

Implementasi Brute Force Algorithm

Algoritma :

Algoritma Bruto Force untuk String Matching saya ambil dari Buku Levitin Bab 3.2. berikut adalah algoritmanya

ALGORITHM BruteForceStringMatch(T[0..n−1],P[0..m−1])
//Implements brute-force string matching
//Input: An arrayT[0..n−1] of n characters representing a text and
// an array P[0..m−1] of m characters representing a pattern
//Output: The index of the first character in the text that starts a
// matching substring or−1 if the search is unsuccessful
fori ←0 to n−m do
j←0
while j<m and P[j]=T[i+j] do
j←j+1
if j=m return i
return−1

Implementasi Program (source code):

#include<iostream>
#include<cstdlib>
#include<string>

using namespace std;

int main()
{
 //input
 string pattern;
 string text;

 //output
 int i, ketemu;

 int j;

 cout << "Masukkan Text : " << endl;
 getline(cin, text); 
 cout << endl;

 cout << "Masukkan Patern" << endl;
 getline(cin, pattern);
 cout << endl;

 int m = pattern.size();
 int n = text.size();

 for(i=0; i<n-m+1; i++)
 {
  j=0;
  //cout << "hai"<< endl;
  while( j<m && pattern[j]==text[i+j])
  {
   j++ ; //cout << "hei"<< endl; 
  }
  if(j==m) break;
 }
 //cout << j << endl;
 if(j==m) cout << "String cocok pada indeks Text ke " << i << endl;
 else cout << "STring tidak ditemukan" << endl;
  

 system("pause");
 return 0;
}

Penjelasan Program :

Input adalah sebuah string Text yaitu string yang berisi kalimat dan sebuah string pattern, yaitukata yang akan dicari dari Text tersebut.

Output adalah sebuah indeks pada Text yang cocok dengan huruf pada string pattern tersebut

cout << "Masukkan Text : " << endl;

       getline(cin, text);

       cout << endl;

       cout << "Masukkan Patern" << endl;

       getline(cin, pattern);

       cout << endl;

kemudian kita lakukan bruto force, yaitu dengan mengecek setiap indeks I pada Text apakah terdapat huruf yang sama dengan huruf –huruf pada pattern. Pengecekan dilakukan setiap huruf pada pattern, bila huruf pertama sama maka akan dilanjutkan mengecek ke huruf pattern selanjutnya. Bila mismatch, maka akan terjadi shift satu ke kanan.

int m = pattern.size();

       int n = text.size();

       for(i=0; i<n-m+1; i++)

       {

              j=0;

              //cout << "hai"<< endl;

              while( j<m && pattern[j]==text[i+j])

              {

                     j++ ; //cout << "hei"<< endl;    

              }

              if(j==m) break;

       }

Jika jumlah huruf yang sama dengan pattern adalah sebesar jumlah huruf pada pattern, maka akan keluar output indeks letak huruf paling kiri pada text yang sama dengan pattern. Jika tidak, maka akan keluar -1 atau disini saya tampilkan “string tidak ditemukan”

       if(j==m) cout << "String cocok pada indeks Text ke " << i << endl;

       else cout << "STring tidak ditemukan" << endl;

Implementasi Horspool Algorithm

Algoritma :

Algoritma Horspool untuk String Matching saya ambil dari Buku Levitin Bab 7.2.2. berikut adalah algoritmanya

ALGORITHM ShiftTable(P[0..m−1])
//Fills the shift table used by Horspool’s and Boyer-Moore algorithms
//Input: PatternP[0..m−1] and an alphabet of possible characters
//Output:Table[0..size−1] indexed by the alphabet’s characters and
// filled with shift sizes computed by formula (7.1)
fori ←0tosize−1doTable[i]←m
forj←0tom−2doTable[P[j]]←m−1−j
returnTable

ALGORITHM HorspoolMatching(P[0..m−1],T[0..n−1])
//Implements Horspool’s algorithm for string matching
//Input: PatternP[0..m−1] and textT[0..n−1]
//Output: The index of the left end of the first matching substring
// or−1 if there are no matches
ShiftTable(P[0..m−1]) //generateTableof shifts
i ←m−1 //position of the pattern’s right end
whilei≤n−1do
k←0 //number of matched characters
whilek≤m−1andP[m−1−k]=T[i−k]do
k←k+1
ifk=m
returni−m+1
elsei ←i+Table[T[i]]
return−1

Implementasi Program(source code) :

#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

//inisialisasi global sebuah tabel sebesar banyaknya huruf alfabet
int tabel[26];

//fungsi tabel yang menyimpan banyaknya shift
int* shiftTable(string pattern)
{
 int m = pattern.size(); //menghitung jumlah panjang pattern
 for(int i=0; i< 256; i++ ) //setiap indeks pada tabel diisi dengan besar panjang pattern
 {
  tabel[i]=m;
 }
 for(int j=0; j< m-1; j++) //untuk mengisi besar shift setiap huruf pada pattern
 {
  tabel[pattern[j]]=m-1-j;
 }
 return tabel;

}

//fungsi horspool
int horspool(string pattern, string text)
{
 shiftTable(pattern); //memanggil fungsi shift table

 int m = pattern.size(); //menghitung panjang string pattern
 int n = text.size(); //menghitung panjang string text

 int i,k;

 i = m-1;

 while(i <= n-1)
 {
  k=0;
  while( k<= m-1 && pattern[m-1-k]==text[i-k] ) //jika huruf pada indeks pattern sama dengan 
  {           //indeks huruf pada Text
   k++ ;

  }
  if(k==m) //apabila jumlah k sama dengan jumlah pattern
  {
   return i-m+1; //menampilkan indeks pada string Text
  }
  else
  {
   i = i + tabel[text[i]];
  }
 
 }
 return -1;
}
int main()
{
 string pattern;
 string text;

 cout << "masukkan Text : " << endl;
 getline(cin, text);
 //cout << text << endl;
 cout << endl;
 cout << "masukkan Pattern : " << endl;
 getline(cin, pattern);
 //cout << pattern << endl;

 int cek = horspool(pattern, text);
 cout << endl;
 //cout << cek;
 if (cek == -1 )
 {
  cout << "String tidak ada " << endl;
 }
 else
 {
  cout << "String cocok dengan Text pada indeks ke : " << cek << endl;
 }

 system("pause");
 return 0;
}

Penjelasan Program :

Pertama membuat shift table terlebih dahulu, yaitu sebuah array integer yang menyimpan informasi berapa jumlah shift bila terjadi mismatch. Untuk shift selain huruf yang ada di pattern, maka akan di default besar shift sejumlah size pattern tersebut

Untuk pengisian shift huruf pada patern yaitu dimulai  dengan aturan m-1-j; m adalah lebar pattern, dan j adalah posisi huruf tersebut pada pattern

int* shiftTable(string pattern)

{

       int m = pattern.size(); //menghitung jumlah panjang pattern

       for(int i=0; i< 256; i++ ) //setiap indeks pada tabel diisi dengan besar panjang pattern

       {

              tabel[i]=m;

       }

       for(int j=0; j< m-1; j++) //untuk mengisi besar shift setiap huruf pada pattern

       {

              tabel[pattern[j]]=m-1-j;

       }

       return tabel;

}

Sama dengan algortima bruteforce sebelumnya, namun disini kaidah shift nya tidak mencoba satu-satu setiap huruf yang ada pada Text, melainkan berdasarkan table shifTable yang telah dicari sebelumnya. Sehingga setiap huruf mempunyai shift tersendiri berdasarkan perhitungan.

int horspool(string pattern, string text)

{

       shiftTable(pattern); //memanggil fungsi shift table

       int m = pattern.size(); //menghitung panjang string pattern

       int n = text.size(); //menghitung panjang string text

       int i,k;

       i = m-1;

       while(i <= n-1)

       {

              k=0;

              while( k<= m-1 && pattern[m-1-k]==text[i-k] ) //jika huruf pada indeks pattern sama dengan

              {                                                                          //indeks huruf pada Text

                     k++ ;

              }

              if(k==m) //apabila jumlah k sama dengan jumlah pattern

              {

                     return i-m+1; //menampilkan indeks pada string Text

              }

              else

              {

                     i = i + tabel[text[i]];

              }

      

       }

       return -1;

}