Calculation of Z - array
int l = 0 , r = 0 ; for ( int i = 1 ; i < N ; i ++ ) { if ( i <= r ) Z [ i ] = min ( r - i + 1 , Z [ i - l ] ) ; while ( i + Z [ i ] < N && S [ Z [ i ] ] == S [ i + Z [ i ] ] ) { Z [ i ] ++ ; } if ( i + Z [ i ] - 1 > r ) { l = i ; r = i + Z [ i ] - 1 ; } }