#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i, n) for (int (i) = 0; (i) < (n); (i)++) #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++) #define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--) #define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--) #define PI acos(-1.0) #define DEBUG(C) cerr << C << endl; #define VI vector #define VII vector #define VL vector #define VLL vector #define VD vector #define VDD vector #define PII pair #define PDD pair #define PLL pair #define VPII vector #define ALL(a) (a).begin(), (a).end() #define SORT(a) sort(ALL(a)) #define REVERSE(a) reverse(ALL(a)) #define MP make_pair #define EB emplace_back #define FORE(a, b) for (auto &&a:b) #define FIND(s, n) (s.find(n) != s.end()) using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9; const int MOD = INF + 7; const LL LLINF = 1e18; class RollingHash { private: const long long mods[2] = {(long long)(1e9 + 7), (long long)(1e9 + 9)}; vector hs[2], pm[2]; vector x; //基数 int len; string S; public: //文字列, 基数1, 基数2 RollingHash(const string& str, long long num1, long long num2) { x.resize(2); x[0] = num1; x[1] = num2; S = str; len = str.length(); for (int i = 0; i < 2; i++) { for (int j = 0; j < len; j++) { pm[i].resize(len + 5); pm[i][0] = 1; for (int j = 0; j < (int)pm[i].size(); j++) { pm[i][j + 1] = (pm[i][j] * x[i]) % mods[i]; } } } init(S); } void init(const string& str) { len = str.length(); for (int i = 0; i < 2; i++) { hs[i].resize(len + 5); hs[i][0] = 0; for (int j = 0; j < len; j++) { hs[i][j + 1] = ((hs[i][j] * x[i]) + str[j]) % mods[i]; } } } //strのハッシュ値生成 pair makeHash(const string& str) { long long res[2]; int slen = str.length(); for (int i = 0; i < 2; i++) { res[i] = 0; for (int j = 0; j < slen; j++) { res[i] = ((res[i] * x[i]) + str[j]) % mods[i]; } } return make_pair(res[0], res[1]); } //S[l..r]のハッシュ値返す pair getHash(int l, int r) { if (l > r) return make_pair(-1, -1); long long res[2]; while (pm[0].size() < r + 5) { for (int i = 0; i < 2; i++) { pm[i].emplace_back((pm[i].back() * x[i]) % mods[i]); } } for (int i = 0; i < 2; i++) { res[i] = (hs[i][r + 1] - (hs[i][l] * pm[i][r - l + 1] % mods[i]) + mods[i]) % mods[i]; } return make_pair(res[0], res[1]); } //Sのハッシュ配列返す vector > getHash() { return vector >{hs[0], hs[1]}; } vector getMod() { return vector {mods[0], mods[1]}; } vector getBaseNum() { return x; } }; int main(void) { string S; cin >> S; random_device rnd; RollingHash r(S, rnd() % MOD, rnd() % MOD); map mp[10]; REP(i, 10) { REP(j, (int)S.size() - i) mp[i][r.getHash(j, j + i)]++; } int M; cin >> M; int ans = 0; REP(i, M) { string s; cin >> s; ans += mp[s.size() - 1][r.makeHash(s)]; } cout << ans << endl; return 0; }