#include #include #include #include #include #include #include using namespace std; using ll = long long; class Trie { public: Trie(){ root = makeNode(); } void insert(string s) { Node* now = root; for(int i = 0; i < (int)s.size(); ++i) { int next = s[i] - 'A'; if(now->child[next] == nullptr) now->child[next] = makeNode(); now = now->child[next]; } now->end = true; } int search(string s) { Node* now = root; int ret = 0; for(int i = 0; i < (int)s.size(); ++i) { ret += now->end; int next = s[i] - 'A'; if(now->child[next] == nullptr) return ret; now = now->child[next]; } return ret + now->end; } private: struct Node { Node* child[26]; bool end; }; Node* root; Node* makeNode() { Node* node = new Node; node->end = false; for(int i = 0; i < 26; ++i) node->child[i] = nullptr; return node; } }; string S, T; int N; int main() { cin >> S >> N; Trie trie; for(int i = 0; i < N; ++i) { cin >> T; trie.insert(T); } int ans = 0; for(int i = 0; i < (int)S.size(); ++i) { ans += trie.search(S.substr(i, (int)S.size() - i)); } cout << ans << endl; return 0; }