1. Algo. Horspool
Kasus 1 dan 2: gada string yg berulang di depan
Kasus 3 dan 4: ada yang berulang
B A R B E R
4 3 2 1 0
(penomoran dari huruf paling akhir ke awal)
Shift Tabel T (berupa array) => index nya sesuai ascii
contoh ascii A = 65 -> T[65] = 4
2. Algo. Boyer-Moore
Ada 2 tabel, yaitu
-> Shift Tabel T
-> Suffix Table utk hitung d2
k = banyaknya variabel yang sama
k = 0 -> Boyer-Moore = Horspool
utk mencari d1
-> Bad-Character (bc) = karakter setelah string yang sama
d1 = max(T[bc] - k, 1)
untuk mencari d2
-> Good Suffix
a. Aturan lama (masih bisa keliru)
d2 = jarak antar karakter yang karakter sebelumnya berbeda
contoh: A B C B A B
(3) (2) (1) (0)
diliat dari karakter paling kanan (B) (nomor 0), karakter sebelumnya A (nomor 1)
lalu sebelum A = karakter B (nomor 2) (sama seperti karakter paling kanan yaitu B), sehingga dilihat, jika karakter sebelumnya = A (karakter di nomor 3 = karakter di nomor 1), maka karakter di nomor 3 bukan merupakan good suffix, dan lihat lagi karakter sebelumnya.
Namun, karena pada contoh, C != A (karakter di nomor 3 != karakter di nomor 1), sehingga C merupakan good suffix dan dihitung jarak dari B (nomor 0) ke B (nomor 2). jarak = 2 -> d2 = 2
Kalau tdk ditemukan good suffix sampai huruf paling awal dari string, maka d2 = jumlah karakter di string tersebut
b. Aturan Baru
//coming soon! kalo ga lupa
Sorting By Counting
contoh:
idx array = [0] [1] [2] [3] [4]
data = 9 8 11 10 12
Tabel Frekuensi
idx array = menyesuaikan data
... [8] [9] [10] [11] [12]
1 1 1 1 1
<- array="" dalam="" data="" jumlah="" p="">
Tabel Distribusi = menyimpan posisi awal data hrs dimasukkan
... [8] [9] [10] [11] [12]
1 1 1 1 1
| | | | |
v v v v v
1 (1+1=2) (2+1=3) (3+1=4) (4+1 = 5)
<- array="" dalam="" data="" jumlah="" p=""><-isi dist.="" p="" tb.="">
<- array="" dalam="" data="" jumlah="" p=""><-isi dist.="" p="" tb.="">karena array dimulai dari index 0, maka nilai di tabel distribusi dikurang dgn 1
sehingga isi dr tabel distribusi:
[0] [1] [2] [3] [4]
0 1 2 3 4
0 comments:
Post a Comment