Implementation of Z - algorithm for linear time pattern searching
def compute_z ( s , z ) : NEW_LINE INDENT l = 0 NEW_LINE r = 0 NEW_LINE n = len ( s ) NEW_LINE for i in range ( 1 , n , 1 ) : NEW_LINE INDENT if ( i > r ) : NEW_LINE INDENT l = i NEW_LINE r = i NEW_LINE while ( r < n and s [ r - l ] == s [ r ] ) : NEW_LINE INDENT r += 1 NEW_LINE DEDENT z [ i ] = r - l NEW_LINE r -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = i - l NEW_LINE if ( z [ k ] < r - i + 1 ) : NEW_LINE INDENT z [ i ] = z [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT l = i NEW_LINE while ( r < n and s [ r - l ] == s [ r ] ) : NEW_LINE INDENT r += 1 NEW_LINE DEDENT z [ i ] = r - l NEW_LINE r -= 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT