#include #include #include #include using namespace std; using i64 = long long; struct rolling_hash { rolling_hash(const string& s, const vector& mods, const vector& bases); i64 calc_hash(int l, int r); // [l, r]。つまりlもrも含む。1-indexed private: string s; vector b[2], H[2]; vector mods, bases; }; template vector segment_sieve(Int a, Int b) { Int sqb = sqrt(b); vector is_prime_small(sqb+1, true); is_prime_small[0] = is_prime_small[1] = false; vector is_prime(b-a, true); is_prime[0] = a != 1; for(Int i=2; i*i res; for(int i=0; i& mods, const vector& bases) : s(s), mods(mods), bases(bases) { int n = s.size(); i64 B; for(int j=0; j<2; ++j) { B = bases[j] % mods[j]; b[j].resize(n+1); H[j].resize(n+1); b[j][0] = 1; H[j][0] = 0; for(int i=0; i primes = segment_sieve(LO, HI); shuffle(begin(primes), end(primes), genrand); vector mods, bases; for(int i=0; i<2; ++i) { mods.push_back(primes[i]); bases.push_back(genrand()); } string s; cin >> s; rolling_hash rhs(s, mods, bases); int n = s.size(); vector> cache(11, vector(n, 0)); for(int len=1; len<=10; ++len) { for(int start=0; start+len<=n; ++start) { cache[len][start] = rhs.calc_hash(start+1, start+len); } } int M; cin >> M; int res = 0; string t; for(int i=0; i> t; int m = t.size(); rolling_hash rht(t, mods, bases); i64 hasht = rht.calc_hash(1, m); for(int start=0; start