Smallest String consisting of a String S exactly K times as a Substring | C ++ Program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int * kmp ( string & s ) { int n = s . size ( ) ; int * lps = new int [ n ] ; lps [ 0 ] = 0 ; int i = 1 , len = 0 ; while ( i < n ) { if ( s [ i ] == s [ len ] ) { len ++ ; lps [ i ] = len ; i ++ ; } else { if ( len != 0 ) { len = lps [ len - 1 ] ; } else { lps [ i ] = 0 ; i ++ ; } } } return lps ; } string findString ( string & s , int k ) { int n = s . length ( ) ; int * lps = kmp ( s ) ; string ans = " " ; string suff = s . substr ( 0 , n - lps [ n - 1 ] ) ; for ( int i = 0 ; i < k - 1 ; ++ i ) { ans += suff ; } ans += s ; return ans ; } int main ( ) { int k = 3 ; string s = " geeksforgeeks " ; cout << findString ( s , k ) << endl ; }