Find the longest sub | Function to find longest prefix suffix ; To store longest prefix suffix ; Length of the previous longest prefix suffix ; lps [ 0 ] is always 0 ; Loop calculates lps [ i ] for i = 1 to n - 1 ; ( pat [ i ] != pat [ len ] ) ; If len = 0 ; Function to find the longest substring which is prefix as well as a sub - string of s [ 1. . . n - 2 ] ; Find longest prefix suffix ; If lps of n - 1 is zero ; At any position lps [ i ] equals to lps [ n - 1 ] ; If answer is not possible ; Driver code ; function call
< ? php function compute_lps ( $ s ) { $ n = strlen ( $ s ) ; $ lps = array ( ) ; $ len = 0 ; $ lps [ 0 ] = 0 ; $ 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 ++ ; } } } return $ lps ; } function Longestsubstring ( $ s ) { $ lps = compute_lps ( $ s ) ; $ n = strlen ( $ s ) ; if ( $ lps [ $ n - 1 ] == 0 ) { echo - 1 ; return ; } for ( $ i = 0 ; $ i < $ n - 1 ; $ i ++ ) { if ( $ lps [ $ i ] == $ lps [ $ n - 1 ] ) { echo substr ( $ s , 0 , $ lps [ $ i ] ) ; return ; } } if ( $ lps [ $ lps [ $ n - 1 ] - 1 ] == 0 ) echo - 1 ; else echo substr ( $ s , 0 , $ lps [ $ lps [ $ n - 1 ] - 1 ] ) ; } $ s = " fixprefixsuffix " ; Longestsubstring ( $ s ) ; ? >