Print the longest prefix of the given string which is also the suffix of the same string | 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
function LengthlongestPrefixSuffix ( s ) { var n = s . length ; var lps = Array . from ( { length : n } , ( _ , i ) => 0 ) ; lps [ 0 ] = 0 ; var len = 0 ; var 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 ++ ; } } } var res = lps [ n - 1 ] ; return ( res > n / 2 ) ? n / 2 : res ; } function longestPrefixSuffix ( s ) { var len = LengthlongestPrefixSuffix ( s ) ; var prefix = " " ; for ( var i = 0 ; i < len ; i ++ ) prefix += s . charAt ( i ) ; return prefix ; } var s = " " ; var ans = longestPrefixSuffix ( s ) ; if ( ans == " " ) document . write ( " " ) ; else document . write ( ans ) ;