#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #include #include #include #include //< in.txt > out.txt using namespace std; //std::ios::sync_with_stdio(false); //std::cin.tie(0); const long long MOD = 1e9 + 7; typedef long long ll; typedef long long LL; typedef long double ld; typedef pair pll; typedef pair pdl; typedef pair pdd; typedef vector VLL; typedef vector VVLL; typedef unsigned long long ULL; //typedef boost::multiprecision::cpp_int bigint; typedef unsigned long long HASH; class RollingHash { public: static const ULL HMOD = (1ULL << 61) - 1; static const ULL MASK30 = (1ULL << 30) - 1; static const ULL MASK31 = (1ULL << 31) - 1; static ULL base; static const ULL POS = HMOD * ((1ULL<<3)-1); static vector powmemo; vector hash; //部分列[0,n)のハッシュを持つ RollingHash(vector& S) { if (base == 0) { random_device rnd; mt19937 mt(rnd()); uniform_int_distribution rand(129, HMOD - 1); RollingHash::base = rand(mt); powmemo.resize(500000, 1); for (LL n = 1; n < 500000; n++) { powmemo[n] = mod(Mul(powmemo[n - 1], base)); } } hash.resize(S.size() + 1); hash[0] = POS; for (ll n = 1; n <= S.size(); n++) { hash[n] = mod(Mul(hash[n - 1], base) + S[n-1]); } } //部分列[a,b)のハッシュ HASH get(LL a, LL b) { return mod(hash[b] + POS - Mul(hash[a], powmemo[b - a])); } //部分列配列への保存なしに変換 HASH conv(vector& S) { HASH ans = 0; for (ll n = 0; n < S.size(); n++) { ans = mod(Mul(ans, base) + S[n]); } return ans; } static HASH Mul(HASH a, HASH b) { HASH au = a >> 31; HASH ad = a & MASK31; HASH bu = b >> 31; HASH bd = b & MASK31; HASH midd = au * bd + ad * bu; HASH midu = midd >> 30; midd = midd & MASK30; return ((au * bu) << 1) + ad * bd + (midd << 31) + midu; } static HASH mod(HASH val) { val = (val & HMOD) + (val >> 61); if (val >= HMOD)val -= HMOD; return val; } }; ULL RollingHash::base = 0; vector RollingHash::powmemo = vector(); int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); string S; cin >> S; ll M; ll ans = 0; vector VS(S.size()); for (ll n = 0; n < S.size(); n++)VS[n] = S[n] - 'A'; RollingHash rh(VS); cin >> M; for (ll m = 0; m < M; m++) { string T; cin >> T; vector VT(T.size()); for (ll n = 0; n < T.size(); n++) VT[n] = T[n] - 'A'; HASH th = rh.conv(VT); for (ll n = 0; n + T.size() <= S.size(); n++) { HASH h = rh.get(n, n + T.size()); if (th == h)ans++; } } cout << ans << "\n"; return 0; }