# Python, clean O(|A| +|B|) KMP

• Not the fastest in Python, meant to be an explanation of KMP technique. Use C++ if you want performance :)

``````class Solution(object):
def repeatedStringMatch(self, s, t):
"""Finds how many repetitions of s are needed to form substring t."""
if len(t) == 0:
return 1
elif len(s) == 0:
return -1

# Before doing any work let's figure out some upper bounds. We have
# two cases:
#
# 1) len(s) <= len(t) -> consider all strings x = s * k where
#    len(x) <= len(s) * 2 + len(t). In the worst case we match the
#    first char of t with the last char of s from which point we
#    match t[1:] sequentially with repetitions of s.
#
# 2) len(s) > len(t) -> consider s and s * 2 only since t cannot span
#    more than 2 s's.
#
# Our strategy is to form a string y = t + # + x and run KMP on it
# until we either find a t in x or exceed the above upper bounds. This
# is going to be a bit strange wince we will start with y = t + # + s
# and expand as needed.

# Like in traditional KMP, kmp[i] = longest proper prefix that is a
# suffix of y[:i + 1]. Initially y = t + # + s so len(y) = len(t) +
# len(s) + 1.
kmp = [0] * (len(t) + len(s) + 1)

def getCharOfY(i):
"""Gets the character at index i in y."""
if i < len(t):
return t[i]
elif i == len(t):
return '#'
else:
return s[(i - len(t) - 1) % len(s)]

i = 1

def lengthOfX():
"""Calculates length of x in y. See explanation above."""
return len(s) if i <= len(t) else i - len(t)

while lengthOfX() <= len(s) * 2 + len(t):
# Expand the table as needed.
if i == len(kmp):
kmp.append(0)

# Calculate kmp[i].
k = kmp[i - 1]
while k > 0 and getCharOfY(k) != getCharOfY(i):
k = kmp[k - 1]

if getCharOfY(k) == getCharOfY(i):
k += 1

# Did we find a t in x?
if k == len(t):
return (lengthOfX() + len(s) - 1) // len(s)

kmp[i] = k
i += 1

return -1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.