#NEWLINE# def maximum_border_length( w ) : #NEWLINE# #INDENT# 'Maximum string borders by Knuth-Morris-Pratt\n\n    :param w: string\n    :returns: table l such that l[i] is the longest border length of w[:i + 1]\n    :complexity: linear\n    ' #NEWLINE# n = len ( w ) #NEWLINE# L = ( [ 0 ] * ( n + 1 ) ) #NEWLINE# for i in range ( 1 , n ) : #NEWLINE# #INDENT# k = L [ i ] #NEWLINE# while ( ( w [ k ] != w [ i ] ) and ( k > 0 ) ) : #NEWLINE# #INDENT# k = L [ k ] #NEWLINE# #UNINDENT# if ( w [ k ] == w [ i ] ) : #NEWLINE# #INDENT# L [ ( i + 1 ) ] = ( k + 1 ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# L [ ( i + 1 ) ] = 0 #NEWLINE# #UNINDENT# #UNINDENT# return L