#include #include #include #include #include using namespace std; #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--) #define chmin(a,b) (a)=min((a),(b)); #define chmax(a,b) (a)=max((a),(b)); #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr< inline void output(const First& first, const Rest&... rest) { cerr << first << " "; output(rest...); } static const int NUM_CHILDREN = 26; static const char MIN_CHAR = 'A'; class Trie { public: bool exist; Trie *next[NUM_CHILDREN]; Trie() : exist(false) { fill(next, next + NUM_CHILDREN, (Trie*)0); } }; void construct(Trie *trie, const vector &strings) { for (auto s : strings) { Trie *p = trie; for (auto c : s) { // cerr << "s = " << s << ", c = " << c << endl; int idx = c - MIN_CHAR; if (!p->next[idx]) p->next[idx] = new Trie; p = p->next[idx]; } p->exist = true; } } void dump(Trie* p, string s) { if (p->exist) cerr << s << endl; for (int i = 0; i < NUM_CHILDREN; ++i) { if (p->next[i]) { dump(p->next[i], s + char(i + MIN_CHAR)); } } } void search(Trie* trie, const string &s, int &cnt) { // cerr << "s = " << s << endl; Trie *p = trie; for (auto c : s) { int idx = c - MIN_CHAR; if (!p->next[idx]) return; p = p->next[idx]; // cerr << "c = " << c << endl; if (p->exist) { cnt++; } } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); string s; cin >> s; int q; cin >> q; vector strings(q); rep(i, q) cin >> strings[i]; Trie *trie = new Trie; construct(trie, strings); // dump(trie, ""); int cnt = 0; rep(i, s.size()) { search(trie, s.substr(i), cnt); } cout << cnt << endl; }