#include using namespace std; #define rep(i,a,b) for(int i=a;i hash_type; int_type base1; int_type base2; int_type mod1; int_type mod2; vector hash1; vector hash2; vector pow1; vector pow2; RollingHash() : base1(1009), base2(1007), mod1(1000000007), mod2(1000000009) {} void init(const string &s) { int n = 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> S >> M; rep(i, 0, M) cin >> C[i]; RollingHash HashS; HashS.init(S); int ans = 0; rep(i, 0, M) { RollingHash HashC; HashC.init(C[i]); rep(j, 0, S.length() - (C[i].length() - 1)) { auto s = HashS.get(j, j + C[i].length()); auto c = HashC.get(0, C[i].length()); if (s == c) ans++; } } cout << ans << endl; }