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


  • 0
    A

    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
    

Log in to reply
 

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