https cpalgorithms comstringprefixfunction html prefix function knuthmorrispratt algorithm different algorithm than knuthmorrispratt pattern finding e x finding longest prefix which is also suffix time complexity on where n is the length of the string for the given string this function computes value for each indexi which represents the longest coincidence of prefix and suffix for given substring inputstr0 i for the value of the first element the algorithm always returns 0 prefixfunctionaabcdaabc 0 1 0 0 0 1 2 3 4 prefixfunctionasdasdad 0 0 0 1 2 3 4 0 list for the result values use last results for better performance dynamic programming prefixfunction use case finding longest prefix which is suffix as well longestprefixaabcdaabc 4 longestprefixasdasdad 4 longestprefixabcab 2 just returning maximum value of the array gives us answer 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 use last results for better performance dynamic programming 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
def prefix_function(input_string: str) -> list:
    

    
    prefix_result = [0] * len(input_string)

    for i in range(1, len(input_string)):
        
        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:
    

    
    return max(prefix_function(input_str))


if __name__ == "__main__":
    import doctest

    doctest.testmod()