#include #include #include #include #include #include #include #include using namespace std; typedef unsigned long long ull; typedef long long ll; struct hash64{ private: const static ull BASE, MOD; vector INV; inline ull MUL(ull a, ull b){ __int128_t t = __int128_t(a) * __int128_t(b); t = (t >> 61) + (t & MOD); return (t>=MOD?t-MOD:t); } inline ull ADD(ull a, ull b){ return (a+b>=MOD?a+b-MOD:a+b); } inline ull SUB(ull a, ull b){ return (a0){ if(b&1) ret = MUL(ret, num); num = MUL(num, num); b /= 2; } for(int i=1;i hashtable(string s){ int n = s.size(); vector ret(n); ull tmp = 0, x = 1; for(int i=0;i &v, int l, int r){ if(l==r) return 0; return MUL(SUB(v[r-1], (l==0?0:v[l-1])), INV[l]); } //tの[l, r)の中にsの[a, b)(固定長)が含まれるか O(max(|r-l| - |b-a|, 0)) inline bool contain(const vector &s, int a, int b, const vector &t, int l, int r){ ull pat = hash(s, a, b); int len = b - a; for(int i=l;i<=r-len;i++){ if(MUL(SUB(t[i+len-1], (i==0?0:t[i-1])), INV[i])==pat) { return true; } } return false; } //lcp(s[a, b), t[l, r)) O(log(len)), len := min(b-a, r-l) inline int lcp(const vector &s, int a, int b, const vector &t, int l, int r){ int L = 0, R = min(b-a, r-l) + 1; while(R-L>1){ int mid = (L+R)/2; if(hash(s, a, a+mid)==hash(t, l, l+mid)) L = mid; else R = mid; } return L; } }; std::random_device seed_gen; std::mt19937_64 engine(seed_gen()); const ull hash64::MOD((1ULL<<61)-1); const ull hash64::BASE(engine()%hash64::MOD); int main(){ string s;std::cin >> s; hash64 h(100000); auto a = h.hashtable(s); int q;scanf("%d", &q); int n = s.size(), ans = 0; for(int i=0;i> t; auto b = h.hashtable(t); int m = t.size(); for(int j=0;j<=n-m;j++){ if(h.hash(a, j, j+m) == b[m-1]) { ans++; } } } printf("%d\n", ans); }