TheAlgorithms-Python

1
"""
2
https://cp-algorithms.com/string/prefix-function.html
3

4
Prefix function Knuth–Morris–Pratt algorithm
5

6
Different algorithm than Knuth-Morris-Pratt pattern finding
7

8
E.x. Finding longest prefix which is also suffix
9

10
Time Complexity: O(n) - where n is the length of the string
11
"""
12

13

14
def prefix_function(input_string: str) -> list:
15
    """
16
    For the given string this function computes value for each index(i),
17
    which represents the longest coincidence of prefix and suffix
18
    for given substring (input_str[0...i])
19

20
    For the value of the first element the algorithm always returns 0
21

22
    >>> prefix_function("aabcdaabc")
23
    [0, 1, 0, 0, 0, 1, 2, 3, 4]
24
    >>> prefix_function("asdasdad")
25
    [0, 0, 0, 1, 2, 3, 4, 0]
26
    """
27

28
    # list for the result values
29
    prefix_result = [0] * len(input_string)
30

31
    for i in range(1, len(input_string)):
32
        # use last results for better performance - dynamic programming
33
        j = prefix_result[i - 1]
34
        while j > 0 and input_string[i] != input_string[j]:
35
            j = prefix_result[j - 1]
36

37
        if input_string[i] == input_string[j]:
38
            j += 1
39
        prefix_result[i] = j
40

41
    return prefix_result
42

43

44
def longest_prefix(input_str: str) -> int:
45
    """
46
    Prefix-function use case
47
    Finding longest prefix which is suffix as well
48

49
    >>> longest_prefix("aabcdaabc")
50
    4
51
    >>> longest_prefix("asdasdad")
52
    4
53
    >>> longest_prefix("abcab")
54
    2
55
    """
56

57
    # just returning maximum value of the array gives us answer
58
    return max(prefix_function(input_str))
59

60

61
if __name__ == "__main__":
62
    import doctest
63

64
    doctest.testmod()
65