Start of ass1

1 files changed, 66 insertions, 0 deletions

diff --git a/w2/w2lab/main.py b/w2/w2lab/main.py
new file mode 100644
index 0000000..2914da3
--- /dev/null
+++ b/w2/w2lab/main.py
@@ -0,0 +1,66 @@
+def naive(string):
+    z = [0 for _ in string]
+    z[0] = len(string)
+    for i in range(1, len(string)):
+        for j in range(0, len(string)):
+            if i+j == len(string) or string[i+j] != string[j]:
+                z[i] = j
+                break
+    return z
+
+
+def naive2(string):
+    z = [0 for _ in string]
+    z[0] = len(string)
+    for i in range(1, len(string)):
+        z[i] = compare(string, i, len(string))
+    return z
+
+
+def compare(string, i, end):
+    for j in range(end):
+        if i+j == end or string[i+j] != string[j]:
+            return j
+
+
+def gusfield(string):
+    z = [0 for _ in string]
+    z[0] = len(string)
+    r = 0
+    l = 0
+    for i in range(1, len(string)):
+        if i == 1:  # base case
+            z[1] = compare(string, i, len(string))
+            if z[1] > 0:
+                r = z[1] + 1
+                l = 1
+        elif i > r: # Case 1
+            z[i] = compare(string, i, len(string))
+            if z[i] > 0:
+                q = i + z[i]
+                r = q - 1
+                l = i
+        elif i <= r:  # Case 2
+            if z[i-l] < r-i:  # 2a
+                print(f"{i} is a case 2a")
+                z[i] = z[i-l]
+            else:  # 2b
+                print(f"{i} is a case 2b")
+                q = compare(string, i, len(string))
+                z[i] = q
+                r = q
+                l = i
+
+    print(f"{l=}, {r=}")
+    return z
+
+
+def main():
+    string = "ababacababa"
+    print(naive2(string))
+    print("="*15)
+    print(gusfield(string))
+
+if __name__ == '__main__':
+    main()
+