Dart

Thanks to this useful post for reminding me that dynamic programming exists (and for linking to a source to help me remember how it works as it always makes my head spin :-) I guessed that part 2 would require counting solutions, so that helped too.

Solves live data in about 40ms.

import 'package:collection/collection.dart';
import 'package:more/more.dart';

int countTarget(String target, Set<String> towels) {
  int n = target.length;
  List<int> ret = List.filled(n + 1, 0)..[0] = 1;

  for (int e in 1.to(n + 1)) {
    for (int s in 0.to(e)) {
      if (towels.contains(target.substring(s, e))) ret[e] += ret[s];
    }
  }
  return ret[n];
}

List<int> allCounts(List<String> lines) {
  var towels = lines.first.split(', ').toSet();
  return lines.skip(2).map((p) => countTarget(p, towels)).toList();
}

part1(List<String> lines) => allCounts(lines).where((e) => e > 0).length;
part2(List<String> lines) => allCounts(lines).sum;