diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | w2lab/main.py | 66 |
2 files changed, 67 insertions, 0 deletions
@@ -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() + |