1 ! Copyright (C) 2010 Dmitry Shubin.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays kernel math ranges sequences sequences.private ;
6 : lcp ( seq1 seq2 -- n )
7 [ min-length dup ] 2keep mismatch-unsafe [ nip ] when* ;
11 :: out-of-zbox ( seq Z l r k -- seq Z l r )
12 seq k tail-slice seq lcp :> Zk
14 Zk 0 > [ k Zk k + 1 - ] [ l r ] if ; inline
16 :: inside-zbox ( seq Z l r k -- seq Z l r )
20 [ Zk' k Z set-nth l r ] ! still inside
22 seq r 1 + seq b [ tail-slice ] 2bi@ lcp :> q
23 q b + k Z set-nth k q r +
26 : z-value ( seq Z l r k -- seq Z l r )
27 2dup < [ out-of-zbox ] [ inside-zbox ] if ; inline
29 :: (z-values) ( seq -- Z )
30 seq length dup 0 <array> :> ( len Z )
32 seq Z 0 0 len [1..b) [ z-value ] each 4drop
37 : z-values ( seq -- Z )
38 [ { } ] [ (z-values) ] if-empty ;