#include using namespace std; using ll = long long; using P = pair; using Graph = vector>; #define rep(i, n) for(ll i=0;i<(ll)(n);i++) #define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++) #define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--) const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; const ll MOD = 1000000007; const ll INF = 1000000000000000000L; #ifdef __DEBUG /** * For DEBUG * https://github.com/ta7uw/cpp-pyprint */ #include "cpp-pyprint/pyprint.h" #endif class RollingHash { static const ll base1 = 1009; static const ll base2 = 2009; static const ll mod1 = 1000000007; static const ll mod2 = 1000000009; vector hash1, hash2, pow1, pow2; public: RollingHash(const string &S) { int n = (int) S.size(); hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); pow1.assign(n + 1, 1); pow2.assign(n + 1, 1); for (int i = 0; i < n; ++i) { hash1[i + 1] = (hash1[i] * base1 + S[i]) % mod1; hash2[i + 1] = (hash2[i] * base2 + S[i]) % mod2; pow1[i + 1] = (pow1[i] * base1) % mod1; pow2[i + 1] = (pow2[i] * base2) % mod2; } } /** * S の [l, r) のハッシュ値を返す * O(1) */ inline pair get(int l, int r) const { ll res1 = hash1[r] - hash1[l] * pow1[r - l] % mod1; if (res1 < 0) res1 += mod1; ll res2 = hash2[r] - hash2[l] * pow2[r - l] % mod2; if (res2 < 0) res2 += mod2; return {res1, res2}; } /** * S のハッシュ値を返す * O(1) */ inline pair hash(const string s) const { return get(0, s.size()); } /** * LCP (Longest Common Prefix) */ inline int getLCP(int a, int b) const { int len = min((int) hash1.size() - a, (int) hash1.size() - b); int low = 0, high = len; while (high - low > 1) { int mid = (low + high) >> 1; if (get(a, a + mid) != get(b, b + mid)) high = mid; else low = mid; } return low; } }; void Main() { string S; int M; cin >> S >> M; vector C(M); rep(i, M) cin >> C[i]; RollingHash rollingHash(S); map target; int N = (int) S.size(); rep(i, N) { rep2(j, 1, 11) { if (i + j <= N) { target[rollingHash.get(i, i + j)]++; } } } int ans = 0; rep(i, M) { string c = C[i]; RollingHash rollingHash1(c); P p = rollingHash1.hash(c); if (target.find(p) != target.end()) { ans += target[p]; } } cout << ans << '\n'; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); Main(); return 0; }