Add Z algorithm implementation and test (#19)

ekzhang · web-flow · commit cf2906b9cc28 · 2021-07-30T10:57:40.000-07:00
diff --git a/src/string_proc.rs b/src/string_proc.rs
@@ -316,6 +316,46 @@ pub fn palindromes(text: &[impl Eq]) -> Vec<usize> {
     pal
 }
 
+//github.com/ Z algorithm for computing an array Z[..], where Z[i] is the length of the
+//github.com/ longest text substring starting from index i that is **also a prefix** of
+//github.com/ the text.
+//github.com/
+//github.com/ This runs in O(n) time. It can be embedded in a larger algorithm, or used
+//github.com/ for string searching as an alternative to KMP above.
+//github.com/
+//github.com/ # Example
+//github.com/
+//github.com/ ```
+//github.com/ use contest_algorithms::string_proc::z_algorithm;
+//github.com/ let z = z_algorithm("ababbababbabababbabababbababbaba".as_bytes());
+//github.com/ assert_eq!(
+//github.com/     z,
+//github.com/     vec![
+//github.com/         32, 0, 2, 0, 0, 9, 0, 2, 0, 0, 4, 0, 9, 0, 2, 0, 0, 4, 0, 13, 0, 2,
+//github.com/         0, 0, 8, 0, 2, 0, 0, 3, 0, 1,
+//github.com/     ],
+//github.com/ );
+//github.com/ ```
+pub fn z_algorithm(text: &[impl Eq]) -> Vec<usize> {
+    let n = text.len();
+    let (mut l, mut r) = (0, 0);
+    let mut z = vec![0; n];
+    z[0] = n;
+    for i in 1..n {
+        if i < r {
+            z[i] = min(r - i, z[i - l]);
+        }
+        while i + z[i] < n && text[i + z[i]] == text[z[i]] {
+            z[i] += 1;
+        }
+        if i + z[i] > r {
+            l = i;
+            r = i + z[i];
+        }
+    }
+    z
+}
+
 #[cfg(test)]
 mod test {
     use super::*;
