Implementation of Z - algorithm for linear time pattern searching
void compute_z ( string s , int z [ ] ) { int l = 0 , r = 0 ; int n = s . length ( ) ; for ( int i = 1 ; i <= n - 1 ; i ++ ) { if ( i > r ) { l = i , r = i ; while ( r < n && s [ r - l ] == s [ r ] ) r ++ ; z [ i ] = r - l ; r -- ; } else { int k = i - l ; if ( z [ k ] < r - i + 1 ) { z [ i ] = z [ k ] ; } else { l = i ; while ( r < n && s [ r - l ] == s [ r ] ) r ++ ; z [ i ] = r - l ; r -- ; } } } }