Skip to content

Instantly share code, notes, and snippets.

@kachayev

kachayev/uniq_substr.hs

Last active December 13, 2015 17:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kachayev/4949030 to your computer and use it in GitHub Desktop.
Save kachayev/4949030 to your computer and use it in GitHub Desktop.
Download ZIP
Define function that returns count of unique substrings consuming O(1) memory
Raw
uniq_substr.hs
import Data.List
uniqSubstr :: String -> Int
uniqSubstr = sum . (map pair) . pairwise . sort . tails
where
pairwise l@(_:ht) = zip l ht
prefix pre post = length $ takeWhile (uncurry (==)) $ zip pre post
pair (pre, post) = length $ drop (prefix pre post) post
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment