diff options
| author | akiyamn | 2021-03-26 18:02:16 +1100 |
|---|---|---|
| committer | akiyamn | 2021-03-26 18:02:16 +1100 |
| commit | ee3534db1311589a868fcf397a20e09b731162ee (patch) | |
| tree | 4c1dc157f25dc719fbf23ca059bb34c3209cf865 /ass1/binary_boyermoore.py | |
| parent | d3be7da60bb9886cb3e0912c6e4f80ccd8c085f5 (diff) | |
| download | fit3155-ee3534db1311589a868fcf397a20e09b731162ee.tar.gz fit3155-ee3534db1311589a868fcf397a20e09b731162ee.zip | |
BM: Fixed things that the merge broke
Diffstat (limited to 'ass1/binary_boyermoore.py')
| -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 |