module Main where
 
import Data.List (nub)
import Data.Map hiding (map)
 
data Trie a x = Trie x (Map a (Trie a x))
 
lzwCompress :: Ord a => [a] -> [a] -> [Int]
lzwCompress cs [] = []
lzwCompress cs xs = loop (length cs) xs id (Trie (-1) d0)
  where
  d0 = fromList (zip cs (map (\n -> Trie n empty) [0..]))
  loop _ []     _ (Trie i _) = [i]
  loop n (x:xs) c (Trie i d)
    | member x d = loop n xs c1 (d ! x)
    | otherwise  = i : loop (n+1) (x:xs) id (c1 (Trie n empty))
    where c1 = c . (\t -> Trie i (insert x t d))
 
lzwDecompress :: [a] -> [Int] -> [a]
lzwDecompress cs is = concat xss
  where
  xss = map (d !!) is
  d = map (:[]) cs ++ zipWith (++) xss (map (take 1) (tail xss))
 
test :: [Char] -> String -> IO ()
test cs xs = do
  putStrLn $ "characters: " ++ cs
  putStrLn $ "uncompressed: " ++ xs
  let comp = lzwCompress cs xs
  putStrLn $ "compressed: " ++ show comp
  putStrLn $ "decompressed: " ++ lzwDecompress cs comp ++ "\n"
 
main :: IO ()
main = do
  test "0123" "010101010"
  test "0123" "01230123012"
  test "0123" "00001110000"
  let akamaki = "akamakigami aomakigami kimakigami"
  test "o kgami" akamaki
  test (nub akamaki) akamaki

bW9kdWxlIE1haW4gd2hlcmUKCmltcG9ydCBEYXRhLkxpc3QgKG51YikKaW1wb3J0IERhdGEuTWFwIGhpZGluZyAobWFwKQoKZGF0YSBUcmllIGEgeCA9IFRyaWUgeCAoTWFwIGEgKFRyaWUgYSB4KSkKCmx6d0NvbXByZXNzIDo6IE9yZCBhID0+IFthXSAtPiBbYV0gLT4gW0ludF0KbHp3Q29tcHJlc3MgY3MgW10gPSBbXQpsendDb21wcmVzcyBjcyB4cyA9IGxvb3AgKGxlbmd0aCBjcykgeHMgaWQgKFRyaWUgKC0xKSBkMCkKICB3aGVyZQogIGQwID0gZnJvbUxpc3QgKHppcCBjcyAobWFwIChcbiAtPiBUcmllIG4gZW1wdHkpIFswLi5dKSkKICBsb29wIF8gW10gICAgIF8gKFRyaWUgaSBfKSA9IFtpXQogIGxvb3AgbiAoeDp4cykgYyAoVHJpZSBpIGQpCiAgICB8IG1lbWJlciB4IGQgPSBsb29wIG4geHMgYzEgKGQgISB4KQogICAgfCBvdGhlcndpc2UgID0gaSA6IGxvb3AgKG4rMSkgKHg6eHMpIGlkIChjMSAoVHJpZSBuIGVtcHR5KSkKICAgIHdoZXJlIGMxID0gYyAuIChcdCAtPiBUcmllIGkgKGluc2VydCB4IHQgZCkpCgpsendEZWNvbXByZXNzIDo6IFthXSAtPiBbSW50XSAtPiBbYV0KbHp3RGVjb21wcmVzcyBjcyBpcyA9IGNvbmNhdCB4c3MKICB3aGVyZQogIHhzcyA9IG1hcCAoZCAhISkgaXMKICBkID0gbWFwICg6W10pIGNzICsrIHppcFdpdGggKCsrKSB4c3MgKG1hcCAodGFrZSAxKSAodGFpbCB4c3MpKQoKdGVzdCA6OiBbQ2hhcl0gLT4gU3RyaW5nIC0+IElPICgpCnRlc3QgY3MgeHMgPSBkbwogIHB1dFN0ckxuICQgImNoYXJhY3RlcnM6ICIgKysgY3MKICBwdXRTdHJMbiAkICJ1bmNvbXByZXNzZWQ6ICIgKysgeHMKICBsZXQgY29tcCA9IGx6d0NvbXByZXNzIGNzIHhzCiAgcHV0U3RyTG4gJCAiY29tcHJlc3NlZDogIiArKyBzaG93IGNvbXAKICBwdXRTdHJMbiAkICJkZWNvbXByZXNzZWQ6ICIgKysgbHp3RGVjb21wcmVzcyBjcyBjb21wICsrICJcbiIKCm1haW4gOjogSU8gKCkKbWFpbiA9IGRvCiAgdGVzdCAiMDEyMyIgIjAxMDEwMTAxMCIKICB0ZXN0ICIwMTIzIiAiMDEyMzAxMjMwMTIiCiAgdGVzdCAiMDEyMyIgIjAwMDAxMTEwMDAwIgogIGxldCBha2FtYWtpID0gImFrYW1ha2lnYW1pIGFvbWFraWdhbWkga2ltYWtpZ2FtaSIKICB0ZXN0ICJvIGtnYW1pIiBha2FtYWtpCiAgdGVzdCAobnViIGFrYW1ha2kpIGFrYW1ha2k=