Longest prefix in a string with highest frequency | C ++ implementation of the above approach ; Function to find Longest prefix string with the highest frequency ; storing all indices where first element is found ; if the first letter in the string does not occur again then answer will be the whole string ; loop till second appearance of the first element ; check one letter after every stored index ; If there is no mismatch we move forward ; otherwise we stop ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void prefix ( string str ) { int k = 1 , j ; int n = str . length ( ) ; vector < int > g ; int flag = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( str [ i ] == str [ 0 ] ) { g . push_back ( i ) ; flag = 1 ; } } if ( flag == 0 ) { cout << str << endl ; } else { int len = g . size ( ) ; while ( k < g [ 0 ] ) { int cnt = 0 ; for ( j = 0 ; j < len ; j ++ ) { if ( str [ g [ j ] + k ] == str [ k ] ) { cnt ++ ; } } if ( cnt == len ) { k ++ ; } else { break ; } } for ( int i = 0 ; i < k ; i ++ ) { cout << str [ i ] ; } cout << endl ; } } int main ( ) { string str = " abcab " ; prefix ( str ) ; return 0 ; }