#include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() template inline bool chmax(A &a, B b) { if (a inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; } typedef unsigned long long ull; typedef long long ll; typedef pair pii; typedef pair pll; typedef pair P; const ll INF = 1ll<<60; const ll MOD = 1000000007; const double EPS = 1e-10; struct RollingHash { vector mod; vector > hs, pw; string s; ll base; int n; RollingHash() {} RollingHash(string s) { init(s); } void init(string _s) { s = _s; n = s.size(); mod.clear(); hs.clear(); pw.clear(); //mod.push_back(999999937); mod.push_back(1000000007); base = 9973; hs.resize(mod.size(), vector(n + 1)); pw.resize(mod.size(), vector(n + 1)); REP(i, mod.size()) { pw[i][0] = 1; REP(j, n) { hs[i][j + 1] = (hs[i][j] + s[j]) * base % mod[i]; pw[i][j + 1] = pw[i][j] * base % mod[i]; } } } inline ll hash(int l, int r, int i) { return (hs[i][r] - hs[i][l] * pw[i][r - l] % mod[i] + mod[i]) % mod[i]; } inline bool match(int l1, int r1, int l2, int r2) { bool res = true; REP(i, mod.size()) if (hash(l1, r1, i) != hash(l2, r2, i)) res = false; return res; } int lcp(int i, int j) { int l = 0, r = min(n - i, n - j) + 1; while (r - l > 1) { int m = (l + r) / 2; if (match(i, i + m, j, j + m)) l = m; else r = m; } return l; } }; int main() { string s; int m; cin >> s >> m; ll ans = 0; RollingHash rh(s); map ss[11]; FOR(i, 1, 11) { REP(j, s.size()) { ss[i][rh.hash(j, j + i, 0)]++; } } REP(i, m) { string c; cin >> c; RollingHash tmp(c); ans += ss[c.size()][tmp.hash(0, c.size(), 0)]; } cout << ans << endl; return 0; }