#include #include #include using namespace std; class Trie { struct Node { int x; map chi; Node() : x(0) {} ~Node() { for(auto kv : chi) { delete kv.second; } } void insert(const string &s) { Node *cur = this; for(size_t i=0, n=s.size(); ichi[s[i]]); if(*nxt == nullptr) { *nxt = new Node; } cur = *nxt; } ++(cur->x); } int calc(const string &s) { Node *cur = this; int res = 0; for(char c : s) { Node **nxt = &(cur->chi[c]); if(*nxt == nullptr) { break; } cur = *nxt; res += cur->x; } return res; } }; public: Node *root; Trie() { root = new Node; } ~Trie() { delete root; } void insert(const string &s) { root->insert(s); } int calc(const string &s) { return root->calc(s); } }; int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); string s; cin >> s; int M; cin >> M; Trie tree; for(int i=0; i> ci; tree.insert(ci); } int res = 0; for(size_t k=0, n=s.size(); k