diff options
Diffstat (limited to 'ass1')
| -rw-r--r-- | ass1/binary_boyermoore.py | 7 |
1 files changed, 4 insertions, 3 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py index 9e00ed2..380eacf 100644 --- a/ass1/binary_boyermoore.py +++ b/ass1/binary_boyermoore.py @@ -94,15 +94,16 @@ def gen_matched_prefix(pat): def preprocess(pat): + R = gen_jump_table(pat) Z = gen_z_suffix(pat) good_suffix = gen_good_suffix(pat, Z) matched_prefix = gen_matched_prefix(pat) - return good_suffix, matched_prefix + return R, good_suffix, matched_prefix def boyer_moore(pat, txt): - good_suffix, matched_prefix = preprocess(pat) + R, good_suffix, matched_prefix = preprocess(pat) m = len(pat) n = len(txt) j = 0 @@ -146,7 +147,7 @@ def boyer_moore(pat, txt): mismatched = txt[j + i] bad_char_shift = i - R[alpha_number(mismatched)][i] good_suffix_shift = 1 - if good_suffix[i+1] >= 0: + if good_suffix[i+1] > 0: good_suffix_shift = m - good_suffix[i+1] gs = True start = good_suffix[i+1] - m + i + 1 |