Maximum number of times a given string needs to be concatenated to form a substring of another string | Function to find lps [ ] for given pattern pat [ 0. . M - 1 ] ; Length of the previous longest prefix suffix ; lps [ 0 ] is always 0 ; Iterate string to calculate lps [ i ] ; If the current character of the pattern matches ; Otherwise ; Otherwise ; Function to implement KMP algorithm ; Stores the longest prefix and suffix values for pattern ; Preprocess the pattern and find the lps [ ] array ; Index for txt [ ] ; Index for pat [ ] ; If pattern is found return 1 ; Mismatch after j matches ; Don 't match lps[0, lps[j - 1]]  characters they will  match anyway ; Return 0 if the pattern is not found ; Function to find the maximum value K for which S2 concatenated K times is a subof S1 ; Store the required maximum number ; Create a temporary to store word ; Store the maximum number of times S2 can occur in S1 ; Traverse in range [ 0 , numWords - 1 ] ; If curWord is found in sequence ; Concatenate word to curWord ; Increment resCount by 1 ; Otherwise break the loop ; Print the answer ; Driver Code ; Function Call
def computeLPSArray ( pat , M , lps ) : NEW_LINE INDENT lenn = 0 NEW_LINE lps [ 0 ] = 0 NEW_LINE i = 1 NEW_LINE while ( i < M ) : NEW_LINE INDENT if ( pat [ i ] == pat [ lenn ] ) : NEW_LINE INDENT lenn += 1 NEW_LINE lps [ i ] = lenn NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( lenn != 0 ) : NEW_LINE INDENT lenn = lps [ lenn - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lps [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def KMPSearch ( pat , txt ) : NEW_LINE INDENT M = len ( pat ) NEW_LINE N = len ( txt ) NEW_LINE lps = [ 0 for i in range ( M ) ] NEW_LINE computeLPSArray ( pat , M , lps ) NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE while ( i < N ) : NEW_LINE INDENT if ( pat [ j ] == txt [ i ] ) : NEW_LINE INDENT j += 1 NEW_LINE i += 1 NEW_LINE DEDENT if ( j == M ) : NEW_LINE INDENT return 1 NEW_LINE j = lps [ j - 1 ] NEW_LINE DEDENT elif ( i < N and pat [ j ] != txt [ i ] ) : NEW_LINE INDENT if ( j != 0 ) : NEW_LINE INDENT j = lps [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT i = i + 1 NEW_LINE DEDENT DEDENT DEDENT return 0 NEW_LINE DEDENT def maxRepeating ( seq , word ) : NEW_LINE INDENT resCount = 0 NEW_LINE curWord = word NEW_LINE numWords = len ( seq ) // len ( word ) NEW_LINE for i in range ( numWords ) : NEW_LINE INDENT if ( KMPSearch ( curWord , seq ) ) : NEW_LINE INDENT curWord += word NEW_LINE resCount += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT print ( resCount ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S1 , S2 = " ababc " , " ab " NEW_LINE maxRepeating ( S1 , S2 ) NEW_LINE DEDENT