anag.hs

import Data.List (tails)
import Data.Map (Map)
import qualified Data.Map as Map

-- <Fuco> heh, this is a nice problem: Given a string A, figure out if string B
--        contains any anagram of A as substring. Example: A = abc, B = de[cab]fh
--        -> true

xs `hasAnagramSubsequence` ys = any (check initialMap) (tails xs)
  where initialMap  = tabulate ys
        check map xs | Map.null map = True
        check map [] = False
        check map (x : xs) = case Map.lookup x map of
          Nothing -> False
          Just 1 -> check (Map.delete x map) xs
          Just n -> check (Map.insert x (n - 1) map) xs

tabulate :: Ord key => [key] -> Map key Int
tabulate = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty

-- "decabfh" `hasAnagramSubsequence` "abc"