Find the longest sub | Z - algorithm function ; bit update function which updates values from index " idx " to last by value " val " ; Query function in bit ; Driver Code ; BIT array ; Making the z array ; update in the bit array from index z [ i ] by increment of 1 ; if the value in z [ i ] is not equal to ( n - i ) then no need to move further ; queryng for the maximum length substring from bit array
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 def update ( idx , val ) : NEW_LINE INDENT global bit NEW_LINE if idx == 0 : NEW_LINE INDENT return NEW_LINE DEDENT while idx <= n : NEW_LINE INDENT bit [ idx ] += val NEW_LINE idx += ( idx & - idx ) NEW_LINE DEDENT DEDENT def pref ( idx ) : NEW_LINE INDENT global bit NEW_LINE ans = 0 NEW_LINE while idx > 0 : NEW_LINE INDENT ans += bit [ idx ] NEW_LINE idx -= ( idx & - idx ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 0 NEW_LINE length = 0 NEW_LINE bit = [ 0 ] * 1000005 NEW_LINE z = [ ] NEW_LINE m = dict ( ) NEW_LINE s = " geeksisforgeeksinplatformgeeks " NEW_LINE z = z_function ( s ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT update ( z [ i ] , 1 ) NEW_LINE DEDENT for i in range ( n - 1 , 1 , - 1 ) : NEW_LINE INDENT if z [ i ] != n - i : NEW_LINE INDENT continue NEW_LINE DEDENT if ( pref ( n ) - pref ( z [ i ] - 1 ) ) >= 2 : NEW_LINE INDENT length = max ( length , z [ i ] ) NEW_LINE DEDENT DEDENT if not length : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( s [ : length ] ) NEW_LINE DEDENT DEDENT