Implementasi Brute Force Algorithm
Implementasi Program (source code):
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;
}
