#include #include using namespace std; const int MOD = 1000000007; const int WORD = 5005; int add(int a, int b) { return (1LL * a + b) % MOD; } int sub(int a, int b) { a %= MOD; b %= MOD; return (a + MOD - b) % MOD; } int mul(int a, int b) { return (1LL * a * b) % MOD; } string txt; int nWord; string word[WORD]; void read() { cin >> txt; cin >> nWord; for (int i = 0; i < nWord; ++i) { cin >> word[i]; } } void work() { map hash2cnt; for (int len = 1; len <= min(10, (int) txt.size()); ++len) { int currHash = 0; for (int i = 0; i < len; ++i) { currHash = add(mul(currHash, 256), txt[i]); } int p = 1; for (int i = 0; i < len; ++i) { p = mul(p, 256); } for (int i = 0; i + len <= txt.size(); ++i) { if (hash2cnt.count(currHash)) { int old = hash2cnt[currHash]; hash2cnt[currHash] = old + 1; } else { hash2cnt[currHash] = 1; } currHash = sub(currHash, mul(p, txt[i])); currHash = mul(currHash, 256); currHash = add(currHash, txt[i + len]); } } int sum = 0; for (int i = 0; i < nWord; ++i) { int targetHash = 0; for (int j = 0; j < word[i].size(); ++j) { targetHash = add(mul(targetHash, 256), word[i][j]); } sum += hash2cnt[targetHash]; } cout << sum << endl; } int main() { read(); work(); return 0; }