Suffix array

:{
import Data.Function
import Data.List

lexSuffixes :: (Ord a) => [a] -> [(Int, [a])]
lexSuffixes xs = sortBy (compare `on` snd) $ scanr (\x (n, xs) -> (n - 1, x : xs)) (length xs + 1, []) xs

naiveSuffix :: (Ord a) => [a] -> [Int]
naiveSuffix = fmap fst . lexSuffixes

-- Length of the longest common prefix.
llcp :: (Eq a) => [a] -> [a] -> Int
llcp xs [] = 0
llcp [] ys = 0
llcp (x : xs) (y : ys) = if x == y then 1 + llcp xs ys else 0

lexConsecutivePrefixes xs = zipWith (\i j ->  (drop (i - 1) xs, drop (j - 1) xs)) (naiveSuffix xs) (drop 1 (naiveSuffix xs))
-- naiveLcp :: (Ord a) => [a] -> [Int]
naiveLcp xs = zipWith (\i j -> llcp (drop (i - 1) xs) (drop (j - 1) xs)) (naiveSuffix xs) (drop 1 (naiveSuffix xs))
--   fmap (\i -> llcp (drop (i - 1) xs) (drop i xs)) (naiveSuffix xs)
:}


lexSuffixes "anpanman"
-- lexSuffixes "ana"
-- lexSuffixes "anpanman"
lexConsecutivePrefixes "anpanman"