@@ -316,6 +316,46 @@ pub fn palindromes(text: &[impl Eq]) -> Vec<usize> {
316316 pal
317317}
318318
319+ /// Z algorithm for computing an array Z[..], where Z[i] is the length of the
320+ /// longest text substring starting from index i that is **also a prefix** of
321+ /// the text.
322+ ///
323+ /// This runs in O(n) time. It can be embedded in a larger algorithm, or used
324+ /// for string searching as an alternative to KMP above.
325+ ///
326+ /// # Example
327+ ///
328+ /// ```
329+ /// use contest_algorithms::string_proc::z_algorithm;
330+ /// let z = z_algorithm("ababbababbabababbabababbababbaba".as_bytes());
331+ /// assert_eq!(
332+ /// z,
333+ /// vec![
334+ /// 32, 0, 2, 0, 0, 9, 0, 2, 0, 0, 4, 0, 9, 0, 2, 0, 0, 4, 0, 13, 0, 2,
335+ /// 0, 0, 8, 0, 2, 0, 0, 3, 0, 1,
336+ /// ],
337+ /// );
338+ /// ```
339+ pub fn z_algorithm ( text : & [ impl Eq ] ) ->Vec < usize > {
340+ let n = text. len ( ) ;
341+ let ( mut l, mut r) =( 0 , 0 ) ;
342+ let mut z =vec ! [ 0 ; n] ;
343+ z[ 0 ] = n;
344+ for iin 1 ..n{
345+ if i < r{
346+ z[ i] =min ( r - i, z[ i - l] ) ;
347+ }
348+ while i + z[ i] < n && text[ i + z[ i] ] == text[ z[ i] ] {
349+ z[ i] +=1 ;
350+ }
351+ if i + z[ i] > r{
352+ l = i;
353+ r = i + z[ i] ;
354+ }
355+ }
356+ z
357+ }
358+
319359#[ cfg( test) ]
320360mod test{
321361use super :: * ;