1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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()
|
