prefix_function.py

"""
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
"""


defprefix_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)

foriinrange(1, len(input_string)):
# use last results for better performance - dynamic programming
j=prefix_result[i-1]
whilej>0andinput_string[i] !=input_string[j]:
j=prefix_result[j-1]

ifinput_string[i] ==input_string[j]:
j+=1
prefix_result[i] =j

returnprefix_result


deflongest_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
returnmax(prefix_function(input_str))


if__name__=="__main__":
importdoctest

doctest.testmod()