# Source code for tryalgo.knuth_morris_pratt

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Find the length of maximal borders by Knuth-Morris-Pratt

jill-jênn vie, christoph dürr et louis abraham - 2014-2019
inspired from a practical lesson (TP) from Yves Lemaire
"""
# pylint: disable=undefined-variable, unused-argument

# snip{ maximum_border_length
[docs]def maximum_border_length(w):
"""Maximum string borders by Knuth-Morris-Pratt

:param w: string
:returns: table f such that f[i] is the longest border length of w[:i + 1]
:complexity: linear
"""
n = len(w)
f =  * n                # init f = 0
k = 0                      # current longest border length
for i in range(1, n):      # compute f[i]
while w[k] != w[i] and k > 0:
k = f[k - 1]       # mismatch: try the next border
if w[k] == w[i]:       # last characters match
k += 1             # we can increment the border length
f[i] = k               # we found the maximal border of w[:i + 1]
return f
# snip}

# snip{ knuth_morris_pratt
[docs]def knuth_morris_pratt(s, t):
"""Find a substring by Knuth-Morris-Pratt

:param s: the haystack string
:param t: the needle string
:returns: index i such that s[i: i + len(t)] == t, or -1
:complexity: O(len(s) + len(t))
"""
sep = '\x00'                   # special unused character
assert sep not in t and sep not in s
f = maximum_border_length(t + sep + s)
n = len(t)
for i, fi in enumerate(f):
if fi == n:                # found a border of the length of t
return i - 2 * n       # beginning of the border in s
return -1
# snip}

# snip{ powerstring_by_border
[docs]def powerstring_by_border(u):
"""Power string by Knuth-Morris-Pratt

:param x: string
:returns: largest k such that there is a string y with x = y^k
:complexity: O(len(x))
"""
f = maximum_border_length(u)
n = len(u)
if n % (n - f[-1]) == 0:       # does the alignment shift divide n ?
return n // (n - f[-1])    # we found a power decomposition
return 1
# snip}

# snip{ powerstring_by_find
[docs]def powerstring_by_find(u):
"""Power string using the python find method

:param x: string
:returns: largest k such that there is a string y with x = y^k
:complexity: O(len(x))
"""
return len(x) // (x + x).find(x, 1)
# snip}