human
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"
How can the above be solved in Python?
 ... Can you provide a code to maximum number of times a given string needs to be concatenated to form a substring of another string and the other steps required?
assistant
#Here is code to maximum number of times a given string needs to be concatenated to form a substring of another string and the other steps required.
 def computeLPSArray ( pat , M , lps ) :
	lenn = 0
	lps [ 0 ] = 0
	i = 1
	while ( i < M ) :
		if ( pat [ i ] == pat [ lenn ] ) :
			lenn += 1
			lps [ i ] = lenn
			i += 1
		else :
			if ( lenn != 0 ) :
				lenn = lps [ lenn - 1 ]
			else :
				lps [ i ] = 0
				i += 1
def KMPSearch ( pat , txt ) :
	M = len ( pat )
	N = len ( txt )
	lps = [ 0 for i in range ( M ) ]
	computeLPSArray ( pat , M , lps )
	i = 0
	j = 0
	while ( i < N ) :
		if ( pat [ j ] == txt [ i ] ) :
			j += 1
			i += 1
		if ( j == M ) :
			return 1
			j = lps [ j - 1 ]
		elif ( i < N and pat [ j ] != txt [ i ] ) :
			if ( j != 0 ) :
				j = lps [ j - 1 ]
			else :
				i = i + 1
	return 0
def maxRepeating ( seq , word ) :
	resCount = 0
	curWord = word
	numWords = len ( seq ) // len ( word )
	for i in range ( numWords ) :
		if ( KMPSearch ( curWord , seq ) ) :
			curWord += word
			resCount += 1
		else :
			break
	print ( resCount )
if __name__ == ' _ _ main _ _ ' :
	S1 , S2 = " ababc " , " ab "
	maxRepeating ( S1 , S2 )