Boyer-Moore bad char rule

1 files changed, 26 insertions, 5 deletions

diff --git a/ass1/editdist.py b/ass1/editdist.py
index ae5b0d1..c00fb69 100644
--- a/ass1/editdist.py
+++ b/ass1/editdist.py
@@ -51,24 +51,45 @@ def comapre_zs(z_prefix, z_suffix, pat_length):
             distance = None
             if z_prefix[i] == pat_length:
                 distance = 0
-            elif z_prefix[i] + z_suffix[i+pat_length-1] >= pat_length-1:
+            elif z_prefix[i] + z_suffix[i] >= pat_length-1:
                 distance = 1
             if distance is not None:
                 file.write(f"{i-pat_length-1} {distance}\n")
                 print(f"===={i-pat_length-1} {distance}")
-            print(i-pat_length-1, z_prefix[i], z_suffix[i+pat_length-1])
-
+            print(i-pat_length-1, z_prefix[i], z_suffix[i])
+
+def match(z_prefix, z_suffix, pat_length):
+    matches = []
+    l = pat_length+1
+    r = len(z_prefix)-1
+    while l < len(z_prefix): # while l hasn't reached the end
+        if z_prefix[l] != 0 and z_suffix[r] != 0:
+            distance = None
+            if z_prefix[l] == pat_length:
+                distance = 0
+            elif z_prefix[l] + z_suffix[r] >= pat_length - 1:
+                distance = 1
+            if distance is not None:
+                matches.append((l-pat_length-1, distance))
+            l += 1
+            r += 1
+        if z_prefix[l] == 0:
+            l += 1
+        if z_suffix[r] == 0:
+            r -= 1
+    return matches
 
 
 def edit_distance(txt, pat):
     forwards = pat + "$" + txt
-    backwards = reverse(pat) + "$" + txt
+    backwards = reverse(pat) + "$" + reverse(txt)
     print(list(forwards))
     print(list(backwards))
     print(gusfield(forwards))
     print(gusfield(backwards))
     print("="*15)
-    comapre_zs(gusfield(forwards), gusfield(backwards), len(pat))
+    # comapre_zs(gusfield(forwards), gusfield(backwards), len(pat))
+    print(match(gusfield(forwards), gusfield(backwards), len(pat)))
 
 def read_args():
     with open(sys.argv[1], "r") as txt_file: