From 527ce5065ae429643433fac3435aeaa8f535e7c1 Mon Sep 17 00:00:00 2001
From: akiyamn
Date: Wed, 10 Mar 2021 20:11:41 +1100
Subject: Finished w2 lab (Z-values)

---
 .gitignore    |  1 +
 w2lab/main.py | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 67 insertions(+)
 create mode 100644 w2lab/main.py

diff --git a/.gitignore b/.gitignore
index 13d1490..40562a6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+.idea
 # ---> Python
 # Byte-compiled / optimized / DLL files
 __pycache__/
diff --git a/w2lab/main.py b/w2lab/main.py
new file mode 100644
index 0000000..2914da3
--- /dev/null
+++ b/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()
+
-- 
cgit v1.2.3