Z - algorithm function
def z_function ( s ) : NEW_LINE INDENT global z , n NEW_LINE n = len ( s ) NEW_LINE z = [ 0 ] * n NEW_LINE l , r = 0 , 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if i <= r : NEW_LINE INDENT z [ i ] = min ( r - i + 1 , z [ i - 1 ] ) NEW_LINE DEDENT while ( i + z [ i ] < n and s [ z [ i ] ] == s [ i + z [ i ] ] ) : NEW_LINE INDENT z [ i ] += 1 NEW_LINE DEDENT if ( i + z [ i ] - 1 > r ) : NEW_LINE INDENT l = i NEW_LINE r = i + z [ i ] - 1 NEW_LINE DEDENT DEDENT return z NEW_LINE DEDENT