Print the longest prefix of the given string which is also the suffix of the same string | Java 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
class GfG { static int LengthlongestPrefixSuffix ( String s ) { int n = s . length ( ) ; int lps [ ] = new int [ n ] ; lps [ 0 ] = 0 ; int len = 0 ; int i = 1 ; while ( i < n ) { if ( s . charAt ( i ) == s . charAt ( 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 ; } static String longestPrefixSuffix ( String s ) { int len = LengthlongestPrefixSuffix ( s ) ; String prefix = " " ; for ( int i = 0 ; i < len ; i ++ ) prefix += s . charAt ( i ) ; return prefix ; } public static void main ( String [ ] args ) { String s = " abcab " ; String ans = longestPrefixSuffix ( s ) ; if ( ans == " " ) System . out . println ( " - 1" ) ; else System . out . println ( ans ) ; } }