#include #include #include #include #include using namespace std; using u64 = uint64_t; u64 uz = time(NULL); inline u64 xorshift64() { uz ^= uz << 18; uz ^= uz >> 19; uz ^= uz << 19; return uz; } struct u128 { u64 hi, lo; u128(u64 _hi, u64 _lo) : hi(_hi), lo(_lo) {} explicit u128(u64 _lo) : u128(0, _lo) {} u128() : u128(0, 0) {} u128 operator + (u128 a) { return u128(hi + a.hi + (lo + a.lo < lo), lo + a.lo); } }; inline u128 mul128(u64 x, u64 y) { u64 hi, lo; __asm__ ("mulq %3" : "=a" (lo), "=d" (hi) : "%0" (x), "rm"(y)); return u128(hi, lo); } template class rolling_hash { static constexpr u64 M = 0xffff'ffff'ffff'ffc5, M2 = 0xcbee'a4e1'a08a'd8f3, R2 = static_cast(-__uint128_t(M) % M); static constexpr u64 mod_add(u64 a, u64 b) { u64 r = a + b; if(r < a) { return r - M; } return r < M ? r : r - M; } static constexpr u64 mod_sub(u64 a, u64 b) { return a < b ? a - b + M : a - b; } static constexpr u64 MR(u128 t) { u128 x = mul128(mul128(t.lo, M2).lo, M); return mod_add(mod_add(x.hi, t.hi), x.lo+t.lo < x.lo); } static constexpr u64 init(u64 x) { return MR(mul128(x, R2)); } static constexpr u64 mod_mul(u64 x, u64 y) { return MR(mul128(x, y)); } T s; u64 b64; size_t n; vector B, H; public: rolling_hash() {} ~rolling_hash() noexcept {} explicit rolling_hash(const T &_s, u64 seed=xorshift64()) : s(_s), b64(seed % M), n(s.size()) { B.resize(n+1); H.resize(n+1); B[0] = init(1); for(size_t i=0; i n || r > n) { return -1; } return calc_hash2(l, r-l+1); } u64 calc_hash2(size_t l, size_t len) const { // l から len 文字。1-indexed. assert(1 <= len); assert(l <= n && l+len <= n+1); return mod_sub(H[l+len-1], mod_mul(B[len], H[l-1])); } }; int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); string s; int m; cin >> s >> m; u64 seed = xorshift64(); rolling_hash rh(s, seed); unordered_map mp; for(size_t i=1, n=s.size(); i<=n; ++i) { for(size_t len=1; len<=10 && i+len<=n+1; ++len) { ++mp[rh.calc_hash2(i, len)]; } } int res = 0; for(int i=0; i> ci; rolling_hash rh2(ci, seed); res += mp[rh2.calc_hash(1, ci.size())]; } cout << res << '\n'; return 0; }