diff options
Diffstat (limited to 'ass1/binary_boyermoore.py')
| -rw-r--r-- | ass1/binary_boyermoore.py | 7 |
1 files changed, 3 insertions, 4 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py index 380eacf..9e00ed2 100644 --- a/ass1/binary_boyermoore.py +++ b/ass1/binary_boyermoore.py @@ -94,16 +94,15 @@ 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 R, good_suffix, matched_prefix + return good_suffix, matched_prefix def boyer_moore(pat, txt): - R, good_suffix, matched_prefix = preprocess(pat) + good_suffix, matched_prefix = preprocess(pat) m = len(pat) n = len(txt) j = 0 @@ -147,7 +146,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 |