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 ; 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 . ; 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
def LengthlongestPrefixSuffix ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE lps = [ 0 for i in range ( n ) ] NEW_LINE len1 = 0 NEW_LINE i = 1 NEW_LINE while ( i < n ) : NEW_LINE INDENT if ( s [ i ] == s [ len1 ] ) : NEW_LINE INDENT len1 += 1 NEW_LINE lps [ i ] = len1 NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( len1 != 0 ) : NEW_LINE INDENT len1 = lps [ len1 - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lps [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT DEDENT res = lps [ n - 1 ] NEW_LINE if ( res > int ( n / 2 ) ) : NEW_LINE INDENT return int ( n / 2 ) NEW_LINE DEDENT else : NEW_LINE INDENT return res NEW_LINE DEDENT DEDENT def longestPrefixSuffix ( s ) : NEW_LINE INDENT len1 = LengthlongestPrefixSuffix ( s ) NEW_LINE prefix = " " NEW_LINE for i in range ( len1 ) : NEW_LINE INDENT prefix += s [ i ] NEW_LINE DEDENT return prefix NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " abcab " NEW_LINE ans = longestPrefixSuffix ( s ) NEW_LINE if ( ans == " " ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ans ) NEW_LINE DEDENT DEDENT