Python KMP O(n)


  • 3
    P
    class Solution(object):
        def repeatedSubstringPattern(self, str):
            """
            :type str: str
            :rtype: bool
            """
            def computeLPS(str):
                lps=[0]*len(str)
                i=1
                length=0
                
                while i<len(str):
                    if str[i]==str[length]:
                        length+=1
                        lps[i]=length
                        i+=1
                    else:
                        if length:
                            length=lps[length-1]
                        else:
                            lps[i]=0
                            i+=1
                return lps 
            
            lps = computeLPS(str)
            n = len(str)
            lenn = lps[-1]
            if lenn and n%(n-lenn)==0:
                return True 
            else:
                return False 
    

  • 0
    W

    @protein.graph I'm comfused about your method . Could you please explain it? thanks


  • 0
    P

    Sorry for late reply,

    But you could do these steps to get an intuition.

    Understand what computing LPS means, KMP algorithm

    In short, it gives the proper longest prefix of string which is also a proper suffix.

    For example, "bcabca" = [0,0,0,1,2,3] and "bcabc" = [0,0,0,1,2]

    Now, if length of string is N, and we find LPS[-1] = L,

    In order to check if the string is periodic, that is string is obtained by repeated substrings,

    we need to check, N>0 and N%(N-L) == 0.


Log in to reply
 

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