Smallest String consisting of a String S exactly K times as a Substring | KMP algorithm ; Function to return the required string ; Finding the longest proper prefix which is also suffix ; ans string ; Update ans appending the substring K - 1 times ; Append the original string ; Returning min length string which contain exactly k substring of given string ; Driver code
def kmp ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE lps = [ None ] * n NEW_LINE lps [ 0 ] = 0 NEW_LINE i , Len = 1 , 0 NEW_LINE while ( i < n ) : NEW_LINE INDENT if ( s [ i ] == s [ Len ] ) : NEW_LINE INDENT Len += 1 NEW_LINE lps [ i ] = Len NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( Len != 0 ) : NEW_LINE INDENT Len = lps [ Len - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lps [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT DEDENT return lps NEW_LINE DEDENT def findString ( s , k ) : NEW_LINE INDENT n = len ( s ) NEW_LINE lps = kmp ( s ) NEW_LINE ans = " " NEW_LINE suff = s [ 0 : n - lps [ n - 1 ] : 1 ] NEW_LINE for i in range ( k - 1 ) : NEW_LINE INDENT ans += suff NEW_LINE DEDENT ans += s NEW_LINE return ans NEW_LINE DEDENT k = 3 NEW_LINE s = " geeksforgeeks " NEW_LINE print ( findString ( s , k ) ) NEW_LINE