Print the longest prefix of the given string which is also the suffix of the same string | C ++ implementation of the approach ; Returns length of the longest prefix which is also suffix and the two do not overlap . This function mainly is copy of computeLPSArray ( ) in KMP Algorithm ; lps [ 0 ] is always 0 ; Length of the previous longest prefix suffix ; Loop to calculate lps [ i ] for i = 1 to n - 1 ; This is tricky . Consider the example . AAACAAAA and i = 7. The idea is similar to search step . ; Also , note that we do not increment i here ; If len = 0 ; Since we are looking for non overlapping parts ; Function that returns the prefix ; Get the length of the longest prefix ; Stores the prefix ; Traverse and add characters ; Returns the prefix ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LengthlongestPrefixSuffix ( string s ) { int n = s . length ( ) ; int lps [ n ] ; lps [ 0 ] = 0 ; int len = 0 ; int i = 1 ; 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 ++ ; } } } int res = lps [ n - 1 ] ; return ( res > n / 2 ) ? n / 2 : res ; } string longestPrefixSuffix ( string s ) { int len = LengthlongestPrefixSuffix ( s ) ; string prefix = " " ; for ( int i = 0 ; i < len ; i ++ ) prefix += s [ i ] ; return prefix ; } int main ( ) { string s = " abcab " ; string ans = longestPrefixSuffix ( s ) ; if ( ans == " " ) cout << " - 1" ; else cout << ans ; return 0 ; }