diff options
Diffstat (limited to 'ass1')
| -rw-r--r-- | ass1/binary_boyermoore.py | 80 |
1 files changed, 24 insertions, 56 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py index a4d286d..f226f6b 100644 --- a/ass1/binary_boyermoore.py +++ b/ass1/binary_boyermoore.py @@ -98,69 +98,37 @@ def boyer_moore(pat, txt): comps = 0 print("="*15) - print(6*" " + txt) + # print(6*" " + txt) + i = m-1 while j <= n-m: - matches = 0 - for i in range(m-1, -1, -1): - # if galil_index == j and start <= i < stop: - # print("pee") - # i = max(start + 1, 1) - # continue - - print(f"{j=:02} {' ' * j}", end="") - for x in range(len(pat)): - if x == i: - print(pat[x].upper(), end="") - else: - print(pat[x], end="") - print() - match = pat[i] == txt[j+i] - comps += 1 - if match: - matches += 1 - if matches == m: - good_suffix_shift = m - matched_prefix[1] - j += good_suffix_shift - i = m-1 - occurrence += 1 - break - else: - mismatched = txt[j+i] - # bad_char_shift = i-R[alpha_number(mismatched)][i] - - good_suffix_shift = 1 - if good_suffix[i+1] > 0: - good_suffix_shift = m - good_suffix[i+1] - start = good_suffix[i+1] - m + i - stop = good_suffix[i+1] - next_galil = j+1 - elif good_suffix[i+1] == 0: - good_suffix_shift = m - matched_prefix[i+1] - start = 1 - stop = matched_prefix[i+1] - next_galil = j+1 - elif matches == m: - print(f"Match at {j}") - good_suffix_shift = m - matched_prefix[1] - # assert good_suffix[i+1] != 0 - # print(start, stop) + match = pat[i] == txt[j+i] + comps += 1 + if match: + if i == 0: + good_suffix_shift = m - matched_prefix[1] j += good_suffix_shift - # print(good_suffix_shift, bad_char_shift) - # if good_suffix_shift >= bad_char_shift: - # print("good suff", good_suffix_shift) - # else: - # print("bad char", bad_char_shift) - # print(i) - # if good_suffix[i+1] >= 0 and good_suffix_shift >= bad_char_shift: - # galil_index = j - break + occurrence += 1 + i = m-1 + else: + i -= 1 + else: + good_suffix_shift = 1 + 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 print(f"It found {occurrence} occurences.") - print(f"\n {list(range(m))}") + # print(f"\n {list(range(m))}") + print("" + str(list(map(int, pat)))) # for i, a in enumerate(R): # print(chr(i+97), a) print(good_suffix) + print(matched_prefix) print(f"{comps} comparisons.") -boyer_moore("010010", "101010111010010101110111010101110100101011101101111011111111111101110111010101110100101011101101101110111010101110100101011101101101110110000110101011101001010111011011011101100001010101110100101011101110101011101001010111011011011101110101011101001010111011011011101110101011101001010111011011011101100001101010111010010101110110110111011000010111011111011101110110101110110101101100000001011001010101010101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010100001011101111101110111011010111011010110110000000101100101010101010101011101001010111011011011101100001011101111101110111011010101110100101011101101101110110000101110111110101010111010010101110110110111011000010111011101010111010010101110110110111011000010111010101110100101011101101101010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101111011000010111011111011101110110101110110101101100000001011001010101010110111110111011101101011101101011011000000010110010101010101111011101110110101110110101101100000001011001010101010111101110110101110110101101100000001011001010101010110101110110101101100000001011001010101010110110111011000010101011101001010111011101010111010010101110110110111011101010111010010101110110110111011101010111010010101110110110111011000011010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111101111111111111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101")
\ No newline at end of file +boyer_moore("111000110", "01110111010101110100101011101101111011111111111111100011001110111010101110100101011101101101110111010110111010010101110110110111011111011011") +# boyer_moore("111011011001110", "101010111010010101110111010101110100101011101101111011111111111101110111010101110100101011101101101110111010101110100101011101101101110111110110110011100000110101011101001010111011011011101100001010101110100101011101110101011101001010111011011011101110101011101001010111011011011101110101011101001010111011011011101100001101010111010010101110110110111011000010111011111011101110110101110110101101100000001011001010101010101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010100001011101111101110111011010111011010110110000000101100101010101010101011101001010111011011011101100001011101111101110111011010101110100101011101101101110110000101110111110101010111010010101110110110111011000010111011101010111010010101110110110111011000010111010101110100101011101101101010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101111011000010111011111011101110110101110110101101100000001011001010101010110111110111011101101011101101011011000000010110010101010101111011101110110101110110101101100000001011001010101010111101110110101110110101101100000001011001010101010110101110110101101100000001011001010101010110110111011000010101011101001010111011101010111010010101110110110111011101010111010010101110110110111011101010111010010101110110110111011000011010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111101111111111111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101")
\ No newline at end of file |