Implementation of Z - algorithm for linear time pattern searching
function compute_z ( s , z ) { var l = 0 , r = 0 ; var n = s . length ; for ( var 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 { var 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 -- ; } } } }