strings.z_function
==================

.. py:module:: strings.z_function

.. autoapi-nested-parse::

   https://cp-algorithms.com/string/z-function.html

   Z-function or Z algorithm

   Efficient algorithm for pattern occurrence in a string

   Time Complexity: O(n) - where n is the length of the string



Functions
---------

.. autoapisummary::

   strings.z_function.find_pattern
   strings.z_function.go_next
   strings.z_function.z_function


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

.. py:function:: find_pattern(pattern: str, input_str: str) -> int

   Example of using z-function for pattern occurrence
   Given function returns the number of times 'pattern'
   appears in 'input_str' as a substring

   >>> find_pattern("abr", "abracadabra")
   2
   >>> find_pattern("a", "aaaa")
   4
   >>> find_pattern("xz", "zxxzxxz")
   2


.. py:function:: go_next(i: int, z_result: list[int], s: str) -> bool

   Check if we have to move forward to the next characters or not


.. py:function:: z_function(input_str: str) -> list[int]

   For the given string this function computes value for each index,
   which represents the maximal length substring starting from the index
   and is the same as the prefix of the same size

   e.x.  for string 'abab' for second index value would be 2

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

   >>> z_function("abracadabra")
   [0, 0, 0, 1, 0, 1, 0, 4, 0, 0, 1]
   >>> z_function("aaaa")
   [0, 3, 2, 1]
   >>> z_function("zxxzxxz")
   [0, 0, 0, 4, 0, 0, 1]