import Data.List
import Data.List.Split
import Debug.Trace

import qualified Data.Vector as V

main :: IO ()
main = do
  input <- readFile "input"
  let [a,b] = splitOn "\n\n" input
  let elements = words $ filter (/= ',') a
  let targets = lines b
--  print $ part1 elements targets
  print $ part2 elements targets

part1 elements targets = count True $ map (canMatch elements) targets
part2 elements targets = sum $ map (numMatches elements) targets

count x xs = length . filter (==x) $ xs


-- with help from claude
canMatch elems s = 
  let n = length s
      matchV = V.generate (n + 1) match
      match i 
        | i == n  = True
        | otherwise = any (\e -> 
            e `isPrefixOf` drop i s &&
            matchV V.! (i + (length e))
            ) elems
  in matchV V.! 0

numMatches elems s = 
  let n = length s
      matchV = V.generate (n + 1) match
      match i 
        | i == n  = 1
        | otherwise = sum $ map (\e -> 
            if e `isPrefixOf` drop i s
            then matchV V.! (i + (length e))
            else 0
            ) elems
  in matchV V.! 0