diff options
| author | akiyamn | 2021-03-25 16:48:48 +1100 |
|---|---|---|
| committer | akiyamn | 2021-03-25 16:48:48 +1100 |
| commit | 4977c9e7dc7a5b4411f8798727a61c8a2e344493 (patch) | |
| tree | 405ea196cab8f9d2d0f84eb5bbaa234c05832f8d /ass1 | |
| parent | 983d590ce17f9dd95319b0e15289b13016d35c58 (diff) | |
| download | fit3155-4977c9e7dc7a5b4411f8798727a61c8a2e344493.tar.gz fit3155-4977c9e7dc7a5b4411f8798727a61c8a2e344493.zip | |
BM: no need to matched prefix?
Diffstat (limited to 'ass1')
| -rw-r--r-- | ass1/binary_boyermoore.py | 15 |
1 files changed, 8 insertions, 7 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py index f226f6b..bbc030f 100644 --- a/ass1/binary_boyermoore.py +++ b/ass1/binary_boyermoore.py @@ -80,14 +80,13 @@ 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 @@ -114,10 +113,8 @@ def boyer_moore(pat, txt): i -= 1 else: good_suffix_shift = 1 - if good_suffix[i+1] > 0: + if good_suffix[i+1] >= 0: good_suffix_shift = m - good_suffix[i+1] - elif good_suffix[i+1] == 0: - good_suffix_shift = m - matched_prefix[i+1] j += good_suffix_shift i = m-1 @@ -126,9 +123,13 @@ def boyer_moore(pat, txt): print("" + str(list(map(int, pat)))) # for i, a in enumerate(R): # print(chr(i+97), a) + print(list(map(lambda x: m - x, good_suffix))) print(good_suffix) print(matched_prefix) print(f"{comps} comparisons.") -boyer_moore("111000110", "01110111010101110100101011101101111011111111111111100011001110111010101110100101011101101101110111010110111010010101110110110111011111011011") +#boyer_moore("2346857", "7263480726134809726305872634582732346857658927635023657293592837562867237968237689035609230896723908029367856087236450823609487623904620934") +boyer_moore("1110001101", "011101110001101010111010010101111100011011111000110111000110101101111011111111111111100011001110111010101110100101011101101101110111010110111010010101110110110111011111011011") + +# boyer_moore("111000110", "01110111010101110100101011101101111011111111111111100011001110111010101110100101011101101101110111010110111010010101110110110111011111011011") # boyer_moore("111011011001110", "101010111010010101110111010101110100101011101101111011111111111101110111010101110100101011101101101110111010101110100101011101101101110111110110110011100000110101011101001010111011011011101100001010101110100101011101110101011101001010111011011011101110101011101001010111011011011101110101011101001010111011011011101100001101010111010010101110110110111011000010111011111011101110110101110110101101100000001011001010101010101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010100001011101111101110111011010111011010110110000000101100101010101010101011101001010111011011011101100001011101111101110111011010101110100101011101101101110110000101110111110101010111010010101110110110111011000010111011101010111010010101110110110111011000010111010101110100101011101101101010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101111011000010111011111011101110110101110110101101100000001011001010101010110111110111011101101011101101011011000000010110010101010101111011101110110101110110101101100000001011001010101010111101110110101110110101101100000001011001010101010110101110110101101100000001011001010101010110110111011000010101011101001010111011101010111010010101110110110111011101010111010010101110110110111011101010111010010101110110110111011000011010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111101111111111111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101")
\ No newline at end of file |