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 - 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
def compute_lps ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE lps = [ 0 for i in range ( n ) ] NEW_LINE Len = 0 NEW_LINE lps [ 0 ] = 0 NEW_LINE i = 1 NEW_LINE while ( i < n ) : NEW_LINE INDENT if ( s [ i ] == s [ Len ] ) : NEW_LINE INDENT Len += 1 NEW_LINE lps [ i ] = Len NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( Len != 0 ) : NEW_LINE INDENT Len = lps [ Len - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lps [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT DEDENT return lps NEW_LINE DEDENT def Longestsubstring ( s ) : NEW_LINE INDENT lps = compute_lps ( s ) NEW_LINE n = len ( s ) NEW_LINE if ( lps [ n - 1 ] == 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE exit ( ) NEW_LINE DEDENT for i in range ( 0 , n - 1 ) : NEW_LINE INDENT if ( lps [ i ] == lps [ n - 1 ] ) : NEW_LINE INDENT print ( s [ 0 : lps [ i ] ] ) NEW_LINE exit ( ) NEW_LINE DEDENT DEDENT if ( lps [ lps [ n - 1 ] - 1 ] == 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( s [ 0 : lps [ lps [ n - 1 ] - 1 ] ] ) NEW_LINE DEDENT DEDENT s = " fixprefixsuffix " NEW_LINE Longestsubstring ( s ) NEW_LINE