1 ! Copyright (C) 2010 Dmitry Shubin.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays help.markup help.syntax sequences ;
8 { "seq1" sequence } { "seq2" sequence }
9 { "n" "a non-negative integer" }
12 "Outputs the length of longest common prefix of two sequences."
17 { "seq" sequence } { "Z" array }
20 "Outputs an array of the same length as " { $snippet "seq" }
21 ", containing Z-values for given sequence. See "
22 { $link "z-algorithm" } " for details."
25 ARTICLE: "z-algorithm" "Z algorithm"
26 { $heading "Definition" }
27 "Given the sequence " { $snippet "S" } " and the index "
28 { $snippet "i" } ", let " { $snippet "i" } "-th Z value of "
29 { $snippet "S" } " be the length of the longest subsequence of "
30 { $snippet "S" } " that starts at " { $snippet "i" }
31 " and matches the prefix of " { $snippet "S" } "."
33 { $heading "Example" }
34 "Here is an example for string " { $snippet "\"abababaca\"" } ":"
36 { { $snippet "i:" } "0" "1" "2" "3" "4" "5" "6" "7" "8" }
37 { { $snippet "S:" } "a" "b" "a" "b" "a" "b" "a" "c" "a" }
38 { { $snippet "Z:" } "9" "0" "5" "0" "3" "0" "1" "0" "1" }
41 { $heading "Summary" }
42 "The " { $vocab-link "z-algorithm" }
43 " vocabulary implements algorithm for finding all Z values for sequence "
45 " in linear time. In contrast to naive approach which takes "
46 { $snippet "Θ(n^2)" } " time."