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