1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <map>
#include <queue>
#include <ranges>
#include <set>
#include <sstream>
#include <string>
#include <string_view>
#include <vector>
using namespace std;
vector<string_view> gettowels(const string_view& line) {
vector<string_view> ret;
unsigned sz = line.size();
for (int i = 0, j = 0; j != -1; i = j+2) {
j = line.find(",", i);
ret.push_back(line.substr(i, (j == -1 ? sz : j) - i));
}
return ret;
}
int64_t f(const string_view& p, const vector<string_view>& towels, vector<int64_t>& mem) {
unsigned lp = p.size();
if (lp == 0) return 1;
if (mem[lp] != -1) return mem[lp];
int64_t ret = 0;
for (auto t : towels) {
unsigned lt = t.size();
if (t == p.substr(0, lt))
ret += f(p.substr(lt, lp - lt), towels, mem);
}
return (mem[lp] = ret);
}
int main() {
string line;
getline(cin, line);
auto towels = gettowels(line);
getline(cin, line);
vector<string> patterns;
while (getline(cin, line))
patterns.push_back(line);
vector<int64_t> mem(1000);
int64_t count = 0;
for (auto p : patterns) {
for (auto& m : mem) m = -1;
count += f(p, towels, mem);
}
cout << count << endl;
return 0;
}
|
