Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.ByteString.ZFunction

Description

Z function calculation.

Definition

\(z[i]\) is defined as the length of the longest common prefix between \(s[0:]\) and \(s[i:]\).

\[ \begin{aligned} z[i] &:= \mathcal{lcp}(s[0:], s[i:]) \end{aligned} \]

Synopsis

lcpOf :: ByteString -> ByteString -> Int
zOfNaive :: ByteString -> Vector Int
zOf :: ByteString -> Vector Int

Documentation

lcpOf :: ByteString -> ByteString -> Int #

\(O(\max(N, M))\) Longest common prefix calculation. \(z[0] := |s|\).

zOfNaive :: ByteString -> Vector Int #

\(O(N^2)\) Z function calculation. \(z[0] := |s|\).

zOf :: ByteString -> Vector Int #

\(O(N)\) Z function calculation. \(z[0] := |s|\).

The \(O(N)\) algorithm

Here is the visualization of intermediate calculation:

String: [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
        [------+------)
         0     |      r' = r0 - l0 + 1
               i' = i - l0
 Z-Box:        [-----+--------)
               l0    i        r0
 Next Z-Box:        [---+---][---+---)
                        |        |
                        |        Known by new search
                        +-- Known by z[i']

\(z[i]\) can be calculated utilizing \(z[i']\) because \(s[i..r] = s[i' .. r']\)