Boyer-Moore to binary

1 files changed, 12 insertions, 4 deletions

diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py
index b42cff7..aa5d0c5 100644
--- a/ass1/binary_boyermoore.py
+++ b/ass1/binary_boyermoore.py
@@ -6,7 +6,7 @@
 # good_suffix = [0 for _ in range(0, m+1)]
 
 def alpha_number(char):
-    return ord(char) - 97
+    return int(char)
 
 
 def reverse(string):
@@ -48,9 +48,9 @@ def gusfield(string):
 
 def gen_jump_table(pat):
     m = len(pat)
-    R = [[-1 for __ in range(m)] for _ in range(0, 26)]
+    R = [[-1 for __ in range(m)] for _ in range(0, 2)]
     for j in range(m):
-        for i in range(j):
+        for i in range(j+1):
             R[alpha_number(pat[i])][j] = i
     return R
 
@@ -95,6 +95,7 @@ def boyer_moore(pat, txt):
     start = None
     stop = None
     galil_index = -1
+    comps = 0
 
     print("="*15)
     print(6*" " + txt)
@@ -115,6 +116,7 @@ def boyer_moore(pat, txt):
                     print(pat[x], end="")
             print()
             match = pat[i] == txt[j+i]
+            comps += 1
             if match:
                 matches += 1
                 if matches == m:
@@ -126,6 +128,7 @@ def boyer_moore(pat, txt):
             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]
@@ -142,8 +145,12 @@ def boyer_moore(pat, txt):
                     good_suffix_shift = m - matched_prefix[1]
                 # print(start, stop)
                 j += max(good_suffix_shift, bad_char_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
@@ -152,5 +159,6 @@ def boyer_moore(pat, txt):
     print(f"\n  {list(range(m))}")
     for i, a in enumerate(R):
         print(chr(i+97), a)
+    print(f"{comps} comparisons.")
 
-boyer_moore("xoxxxo", "xooxxoxoxoxoxoxoxxxoxxoxxxoxxoooxxxoxxxoxxxox")
\ No newline at end of file
+boyer_moore("111101111111111", "101010111010010101110111010101110100101011101101111011111111111101110111010101110100101011101101101110111010101110100101011101101101110110000110101011101001010111011011011101100001010101110100101011101110101011101001010111011011011101110101011101001010111011011011101110101011101001010111011011011101100001101010111010010101110110110111011000010111011111011101110110101110110101101100000001011001010101010101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010100001011101111101110111011010111011010110110000000101100101010101010101011101001010111011011011101100001011101111101110111011010101110100101011101101101110110000101110111110101010111010010101110110110111011000010111011101010111010010101110110110111011000010111010101110100101011101101101010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101111011000010111011111011101110110101110110101101100000001011001010101010110111110111011101101011101101011011000000010110010101010101111011101110110101110110101101100000001011001010101010111101110110101110110101101100000001011001010101010110101110110101101100000001011001010101010110110111011000010101011101001010111011101010111010010101110110110111011101010111010010101110110110111011101010111010010101110110110111011000011010101110100101011101101101110110000101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101101110111110111011101101011101101011011000000010110010101010101011101111101110111011010111011010110110000000101100101010101010000101110111110111011101101011101101011011000000010110010101010101000010111011111011101110110101110110101101100000001011001010101010101010111101111111111111010010101110110110111011000010111011111011101110110101011101001010111011011011101100001011101111101010101110100101011101101101110110000101110111010101110100101011101101101110110000101110101011101001010111011011010101011101001010111011011011101100001011101111101110111011010111011010110110000000101100101010101011110110000101110111110111011101101011101101011011000000010110010101010101101111101110111011010111011010110110000000101100101010101011110111011101101011101101011011000000010110010101010101111011101101011101101011011000000010110010101010101101011101101011011000000010110010101010101101101110110000101110111110111011101101011101101011011000000010110010101010101")
\ No newline at end of file