BM: no need to matched prefix?

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