Asslaamualaikum wr.wb.
pada kesempatan kali ini kita akan memabahas apa itu Algoritma String Matching Z, yang biasanya kita hanya menemukan Algoritma String MAthcing , antara lain : Brute Force, KMP, dan Boyer Moore. Akan tetapi masih banyak lagi Alagoritma-algoritma lain yang dapat digunakan untuk menyelesaikan permasalahan String Matching contohnya ALgoritma Z, Berikut adalah penjelasanya :
Diskripsi Algoritma Z :
Algoritma Z merupakan suatu pola pencarian sebuah sub string
dalam suatu text dengan waktu liner. Total waktu yang dibutuhkan dalam
menjalankan algoritma ini adalah O(m+n), dengan m adalah panjang pola dan n
adalah panjang text. Algoritma Z memilii
kompleksitas waktu yang sama dengan algoritma KMP tetapi algoritma ini lebih
sederhana untuk diapahami.
Z array adalah array yang menyimpan substring terpanjang
mulai dari str[i].
Cara kerja Algoritma Z :
Pertama program akan mendeklarasikan sebuah variabel L,R,k yang
akan digunakan sebagai indeks untuk membandingkan text. Penjelasan variabel :
·
R = indeks right digunakan sebagai pointer yang
berjalan ke arah kanan atau menunjuk nilai yang ada disebelah kanan.
·
L= indeks Left digunakan
sebagai pointer untuk menunjuk nilai di sebelah kiri.
Algoritma ini
menggunakan looping for dengan indeks awal i=1 hingga kurang dari n, n
merupakan panjang pattren. Pada looping terdapat 2 kondisi, berikut penjelasan
dari kondisi tersebut :
·
If (i > R), bila indeks
i lebih besar dari indeks right maka
akan membandingkan char pada array. Indeks L selalu sama dengan indeks i,
sedangkan indeks R akan bertambah satu ketika char yang dibandingkan memiliki
nilai yang sama. Perbandingan antar char dilakukan dengan menggunakan looping
while, saat looping berhenti array Z akan menyimpan banyak nilai yang sama.
·
Else, jika nilai i kurang dari index R maka akan membandingkan
char antara interval L-R dengan interval L-R yang sama pada indeks sebelumnya, jika
z array pada indeks i-L kurang dari R-i-1 maka isi dari z box pada indeks
tersebut sama dengan z array pada indeks k. Jika lebih besar berarti pada indeks itu
terdapat char dengan nilai yang sama, maka akan terjadi proses looping hingga
char tidak sama. Selama proses looping variabel R akan ditambah 1. Sehingga
nanti pada z array akan bernilai R-L (banyak char yang sama).
Mungkin Cukup sekalian, jika kalau ada komplain atau request materi bisa komen di kolom komentar
terimakasih :)
wasalamualaikum wr.wb
0 Comments