#include using namespace std; #define SZ(x) (int) (x).size() #define REP(i, n) for(int i = 0; i < (n); i++) #define FOR(i, a, b) for(auto i = (a); i < (b); i++) #define For(i, a, b, c) \ for(auto i = (a); i != (b); i += (c)) #define REPR(i, n) for(auto i = (n) -1; i >= 0; i--) #define ALL(s) (s).begin(), (s).end() #define so(V) sort(ALL(V)) #define rev(V) reverse(ALL(V)) #define uni(v) v.erase(unique(ALL(v)), (v).end()) #define eb emplace_back typedef long long unsigned int llu; typedef long long ll; typedef vector vi; typedef vector vll; typedef vector vb; typedef vector vvi; typedef vector vvll; typedef pair PI; typedef pair PL; const double EPS = 1e-9; const int MOD = 1e9 + 7; const int INF = (1 << 30); const ll LINF = 1e18; const double math_PI = acos(-1); template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, Ts... ts) { return vector(ts...))>( a, make_v(ts...)); } template typename enable_if::value == 0>::type fill_v( T& t, const V& v) { t = v; } template typename enable_if::value != 0>::type fill_v( T& t, const V& v) { for(auto& e: t) fill_v(e, v); } template bool chmax(T& a, const T& b) { if(a < b) { a = b; return true; } return false; } template bool chmin(T& a, const T& b) { if(a > b) { a = b; return true; } return false; } template istream& operator>>(istream& is, pair& p) { cin >> p.first >> p.second; return is; } template istream& operator>>(istream& is, vector& vec) { for(T& x: vec) is >> x; return is; } template string join(vector& vec, string splitter) { stringstream ss; REP(i, SZ(vec)) { if(i != 0) ss << splitter; ss << vec[i]; } return ss.str(); } template ostream& operator<<(ostream& os, vector& vec) { os << join(vec, " "); return os; } struct RollingHash { private: static const uint64_t mod = (1ull << 61ull) - 1; using uint128_t = __uint128_t; static inline uint64_t base1 = 0, base2 = 0; static inline vector pow1, pow2; vector hash1, hash2; // 必要分のpow配列を追加で求める。 inline void expand(int sz) { int pre_sz = SZ(pow1); if(pre_sz < sz + 1) { for(int i = pre_sz - 1; i < sz; i++) { pow1.push_back(mul(pow1[i], base1)); pow2.push_back(mul(pow2[i], base2)); } } } static inline uint64_t add(uint64_t a, uint64_t b) { if((a += b) >= mod) a -= mod; return a; } static inline uint64_t mul(uint64_t a, uint64_t b) { uint128_t c = (uint128_t) a * b; return add(c >> 61, c & mod); } public: /// @brief 指定した文字列に対して,ハッシュを前計算する /// @param s ハッシュを取る文字列 RollingHash(const string& s) : RollingHash(vector(s.begin(), s.end())) { } /// @brief 指定した配列に対して,ハッシュを前計算する /// @param s ハッシュを取る配列 template RollingHash(const vector& s) { if(base1 == 0) { mt19937_64 mt(chrono::steady_clock::now() .time_since_epoch() .count()); uniform_int_distribution rand( 1e9, RollingHash::mod - 1); base1 = rand(mt); base2 = rand(mt); } pow1.push_back(1); pow2.push_back(1); expand(SZ(s) + 1); hash1 = vector(SZ(s) + 1); hash2 = vector(SZ(s) + 1); REP(i, SZ(s)) { hash1[i + 1] = add(mul(hash1[i], base1), s[i]); hash2[i + 1] = add(mul(hash2[i], base2), s[i]); } } /// @brief build関数で計算されたhash値をもとにbegin文字目からlength文字のhash値を求める /// @param begin 文字列の初期位置(0-indexed) /// @param length 文字列の長さ /// @return 2通りのhash値 pair query(int begin, int length) { assert(begin + length <= SZ(hash1)); assert(begin >= 0); assert(length > 0); expand(length); return { add(hash1[begin + length], mod - mul(hash1[begin], pow1[length])), add(hash2[begin + length], mod - mul(hash2[begin], pow2[length])) }; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); string S; cin >> S; RollingHash HS(S); map, int> m; REP(i, SZ(S)) { FOR(len, 1, 11) { if(i + len > SZ(S)) break; m[HS.query(i, len)]++; } } int M; cin >> M; int ans = 0; REP(i, M) { string C; cin >> C; RollingHash HC(C); ans += m[HC.query(0, SZ(C))]; } cout << ans << endl; return 0; }