#!/usr/bin/perl
use v5.35.0;

# OK, so 2.pl is acceptably quick, but this is quicker still.
#
# The basic approach is the same - finding all the available parts that are
# prefixes of the overall pattern we're trying to make - but instead of
# keeping the available parts in a sorted list and calling out to a function
# to search that list and get matching prefixes from it, we just keep all
# the parts in a prefix tree from the get-go.
#
# The prefix tree is made out of arrays rather than hashes because Perl is
# faster at array indexing than hash lookup. Those arrays are indexed using
# mapped character codes assigned sequentially from 1 upward as newly seen
# input bytes arrive, just to keep them as small as they can be for any
# given selection of input bytes. This mapping also guarantees that zero,
# which no input byte ever maps to, is available as an end-of-input marker.
#
# Each node in the tree is an array with one slot per mapped character code.
# If the slot for a particular character code is defined in the root node,
# a string starting with that code (i.e. having that code at offset 0) has
# been stored within the tree. Nodes one level removed from the root contain
# entries for codes at offset 1 within ther stored strings, nodes twice
# removed from the root are for codes at offset 2 and so on.
#
# If entry 0 in any node is defined, then a *complete* input string leading
# to that node, whose length is equal to the depth of the node, has been
# stored in the tree. There may also be longer strings, of which that
# complete string is a prefix, stored in it as well; if there are, then
# entries for their Nth character will exist within the same node.
#
# Entry 0 within any node is just a simple counter. The way the tree is
# built guarantees that if it's defined at all it will be nonzero, so it's
# safe to test it for truthiness, not merely for definedness. All the other
# entries within the node are either undefined or references to child nodes,
# and since Perl considers any reference value to be truthy, their truthiness
# and definedness are likewise equivalent.
#
# This scheme creates a *lot* less work than doing searches, even nice tight
# binary searches, against a conventional sorted list for every input byte
# that might be part of a prefix. That lets this version run four to five
# times as fast as 2.pl. It's also a lot shorter.

my $lastcode = 0;
my @codes;
my @prefix_tree;

while (<>) {
	chomp;
	last if /^$/;
	for (split /,\s*/) {
		my $node = \@prefix_tree;
		$node = $$node[$codes[$_] //= ++$lastcode] //= [] for unpack 'C*';
		$$node[0]++;
	}
}

my $total = 0;
while (<>) {
	chomp;
	$total += ways_to_make($_, map {$codes[$_] //= ++$lastcode} unpack 'C*');
}
say $total;

sub ways_to_make {
	my $s = shift;
	return 1 unless @_;

	state %memo;
	return $memo{$s} if exists $memo{$s};

	my $ways = 0;
	my $node = \@prefix_tree;
	while (@_) {
		last unless $node = $$node[shift];
		$ways += ways_to_make(substr($s, -@_), @_) if $$node[0];
	}

	return $memo{$s} = $ways;
}