strings.prefix_function
=======================

.. py:module:: strings.prefix_function

.. autoapi-nested-parse::

   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



Functions
---------

.. autoapisummary::

   strings.prefix_function.longest_prefix
   strings.prefix_function.prefix_function


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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]