gistfile1.hs

import Data.List (tails,sort)

-- build suffix array
build :: Ord a => [a] -> [[a]]
build = sort.tails

-- binary search
bs [] str  = False
bs [x] str = cmp str x
bs xs str 
    | cmp str x    = True
    | str < x      = bs l str
    | otherwise    = bs r str
   where (l,x:r)    = splitAt (length xs `div` 2) xs

-- partial compare
cmp str x = (length x >= length str) && (subcmp str x)
subcmp []  _      = True
subcmp (s:ss) (n:ns)
    | s == n    = subcmp ss ns
    | otherwise = False