extra/z-algorithm/z-algorithm-docs.factor

   1 ! Copyright (C) 2010 Dmitry Shubin.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: arrays help.markup help.syntax sequences ;
   4 IN: z-algorithm
   5
   6 HELP: lcp
   7 { $values
   8   { "seq1" sequence } { "seq2" sequence }
   9   { "n" "a non-negative integer" }
  10 }
  11 { $description
  12   "Outputs the length of longest common prefix of two sequences."
  13 } ;
  14
  15 HELP: z-values
  16 { $values
  17   { "seq" sequence } { "Z" array }
  18 }
  19 { $description
  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."
  23 } ;
  24
  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" } "."
  32
  33 { $heading "Example" }
  34 "Here is an example for string " { $snippet "\"abababaca\"" } ":"
  35 { $table
  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" }
  39 }
  40
  41 { $heading "Summary" }
  42 "The " { $vocab-link "z-algorithm" }
  43 " vocabulary implements algorithm for finding all Z values for sequence "
  44 { $snippet "S" }
  45 " in linear time. In contrast to naive approach which takes "
  46 { $snippet "Θ(n^2)" } " time."
  47 ;
  48
  49 ABOUT: "z-algorithm"