Boyer-Moore bad char rule

1 files changed, 27 insertions, 0 deletions

diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py
new file mode 100644
index 0000000..1d60f52
--- /dev/null
+++ b/ass1/binary_boyermoore.py
@@ -0,0 +1,27 @@
+txt = "xpbctbxabacbxtbpqa"
+pat = "tbapxab"
+m = len(pat)
+n = len(txt)
+R = [m for _ in range(0, 26)]
+
+def alpha_number(char):
+    return ord(char) - 97
+
+for i in range(m):
+    R[alpha_number(pat[i])] = i
+
+j = 0
+while j < n-m:
+    for i in range(m-1, -1, -1):
+        print(j)
+        match = pat[i] == txt[j+i]
+        if match:
+            pass
+            # print(i)
+        else:
+            mismatched = txt[j+i]
+            shift = i-R[alpha_number(mismatched)]
+            j += max(1, shift)
+            if j > n-m:
+                break
+print(R)
\ No newline at end of file