use std::{collections::HashMap, io::Read};

use anyhow::Result;
use nom::IResult;
use trie_hard::TrieHard;

fn main() -> Result<()> {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input)?;

    let (_, input) = parse_input(&input).unwrap();

    let mut possible = 0;
    let mut rearrangements = 0;

    for wanted in &input.wanted {
        let res = get_towels_for_patterns(wanted, &input.towels, &mut HashMap::new());
        possible += res.min(1);
        rearrangements += res;
    }

    eprintln!("{possible}");
    eprintln!("{rearrangements}");

    Ok(())
}

fn get_towels_for_patterns<'b>(
    wanted: &'b str,
    towels: &TrieHard<'_, &'_ str>,
    cache: &mut HashMap<&'b str, u64>,
) -> u64 {
    if wanted.is_empty() {
        return 1;
    }

    let mut possibilities = 0;

    for i in (0..wanted.len()).rev() {
        let (wanted, rest) = wanted.split_at(i + 1);

        if towels.get(wanted).is_some() {
            if let Some(cached) = cache.get(rest) {
                possibilities += cached;
                continue;
            }

            let value = get_towels_for_patterns(rest, towels, cache);
            cache.insert(rest, value);
            possibilities += value;
        }
    }

    possibilities
}

#[derive(Debug)]
pub struct Input<'a> {
    towels: TrieHard<'a, &'a str>,
    wanted: Vec<&'a str>,
}

fn parse_input(input: &str) -> IResult<&str, Input> {
    use nom::{
        bytes::complete::tag, character::complete::alpha1, combinator::map, multi::separated_list1,
        sequence::separated_pair,
    };

    let parse_towels = map(separated_list1(tag(", "), alpha1), TrieHard::from_iter);
    let parse_wanted = separated_list1(tag("\n"), alpha1);

    map(
        separated_pair(parse_towels, tag("\n\n"), parse_wanted),
        |(towels, wanted)| Input { towels, wanted },
    )(input)
}