Maximum number of times a given string needs to be concatenated to form a substring of another string | Java program for the above approach ; 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 string S2 concatenated K times is a substring of string S1 ; Store the required maximum number ; Create a temporary string to store string word ; Store the maximum number of times string S2 can occur in string 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
class GFG { static void computeLPSArray ( String pat , int M , int [ ] lps ) { int len = 0 ; lps [ 0 ] = 0 ; int i = 1 ; while ( i < M ) { if ( pat . charAt ( i ) == pat . charAt ( len ) ) { len ++ ; lps [ i ] = len ; i ++ ; } else { if ( len != 0 ) { len = lps [ len - 1 ] ; } else { lps [ i ] = 0 ; i ++ ; } } } } static int KMPSearch ( String pat , String txt ) { int M = pat . length ( ) ; int N = txt . length ( ) ; int lps [ ] = new int [ M ] ; computeLPSArray ( pat , M , lps ) ; int i = 0 ; int j = 0 ; while ( i < N ) { if ( pat . charAt ( j ) == txt . charAt ( i ) ) { j ++ ; i ++ ; } if ( j == M ) { return 1 ; else if ( i < N && pat . charAt ( j ) != txt . charAt ( i ) ) { if ( j != 0 ) j = lps [ j - 1 ] ; else i = i + 1 ; } } return 0 ; } static void maxRepeating ( String seq , String word ) { int resCount = 0 ; String curWord = word ; int numWords = seq . length ( ) / word . length ( ) ; for ( int i = 0 ; i < numWords ; i ++ ) { if ( KMPSearch ( curWord , seq ) == 1 ) { curWord += word ; resCount ++ ; } else break ; } System . out . print ( resCount ) ; } public static void main ( String [ ] args ) { String S1 = " ababc " , S2 = " ab " ; maxRepeating ( S1 , S2 ) ; } }