Jelaskan Pseudocode dari Algoritma Boyer-Moore

Berikut adalah pseudocode algoritme Boyer-Moore pada fase pra-pencarian:

input P: array[0..n-1] of char,

input/output bmBc: array[0..n-1] of integer

for (i:= 0 to ASIZE-1)

for (i:= 0 to m - 2)

bmBc[P[i]]:= m - i - 1;

input P: array[0..n-1] of char,

input/output suff: array[0..n-1] of integer

for (i:= n - 2 downto 0) {

if (i > g and (suff[i + n - 1 - f] < i - g))

suff[i]:= suff[i + n - 1 - f];

while (g >= 0 and P[g] = P[g + n - 1 - f])

suff[i] = f - g;

input P: array[0..n-1] of char,

input/output bmBc: array[0..n-1] of integer

suff: array [0..RuangAlpabet] of integer

for (i:= 0 to m-1)

for (i:= n - 1 downto 0)

if (suff[i] = i + 1)

for (j:=j to n - 2 - i)

bmGs[j]:= n - 1 - i

for (i = 0 to n - 2)

bmGs[n - 1 - suff[i]]:= n - 1 - i;

Dan berikut adalah pseudocode algoritme Boyer-Moore pada fase pencarian:

input P: array[0..n-1] of char,

input T: array[0..m-1] of char,

output ketemu: array[0..m-1] of boolean

i, j, shift, bmBcShift, bmGsShift: integer

while (j >=0 n and T[i+j] = P[j]) do

Tabel untuk penggeseran bad-character dan good-suffix dapat dihitung dengan kompleksitas waktu dan ruang sebesar O(n + σ) dengan σ adalah besar ruang alfabet. Sedangkan pada fase pencarian, algoritme ini membutuhkan waktu sebesar O(mn), pada kasus terburuk, algoritme ini akan melakukan 3n pencocokkan karakter, namun pada performa terbaiknya algoritme ini hanya akan melakukan O(m/n) pencocokkan.