Main.hs

module Main where

main :: IO ()
main = interact $ \ input ->
  let (serializedTree:encodedMessages) = lines input
      tree = deserialize serializedTree
      messages = map (decode tree) encodedMessages in
  unlines messages

data PrefixTree = Leaf Char | Node PrefixTree PrefixTree

deserialize :: String -> PrefixTree
deserialize string = deserialize' (reverse string) []
  where
    deserialize' [] (root:_) = root
    deserialize' ('*':string) (l:r:stack) = deserialize' string ((Node l r):stack)
    deserialize' (char:string) stack = deserialize' string ((Leaf char):stack)

decode :: PrefixTree -> String -> String
decode tree string = decode' tree string
  where
    decode' (Leaf char) string = char:(decode' tree string)
    decode' (Node l r) (char:string) = decode' (if char == '0' then l else r) string
    decode' _ [] = []