Repository navigation
Expand file tree
/
Copy pathprefix_function.py
More file actions
64 lines (45 loc) · 1.58 KB
/
Copy pathprefix_function.py
File metadata and controls
64 lines (45 loc) · 1.58 KB
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
"""
https://cp-algorithms.com/string/prefix-function.html
Prefix function Knuth-Morris-Pratt algorithm
Different algorithm than Knuth-Morris-Pratt pattern finding
E.x. Finding longest prefix which is also suffix
Time Complexity: O(n) - where n is the length of the string
"""
def prefix_function(input_string: str) -> list:
"""
For the given string this function computes value for each index(i),
which represents the longest coincidence of prefix and suffix
for given substring (input_str[0...i])
For the value of the first element the algorithm always returns 0
>>> prefix_function("aabcdaabc")
[0, 1, 0, 0, 0, 1, 2, 3, 4]
>>> prefix_function("asdasdad")
[0, 0, 0, 1, 2, 3, 4, 0]
"""
# list for the result values
prefix_result = [0] * len(input_string)
for i in range(1, len(input_string)):
# use last results for better performance - dynamic programming
j = prefix_result[i - 1]
while j > 0 and input_string[i] != input_string[j]:
j = prefix_result[j - 1]
if input_string[i] == input_string[j]:
j += 1
prefix_result[i] = j
return prefix_result
def longest_prefix(input_str: str) -> int:
"""
Prefix-function use case
Finding longest prefix which is suffix as well
>>> longest_prefix("aabcdaabc")
4
>>> longest_prefix("asdasdad")
4
>>> longest_prefix("abcab")
2
"""
# just returning maximum value of the array gives us answer
return max(prefix_function(input_str))
if __name__ == "__main__":
import doctest
doctest.testmod()