#include #include #include using namespace std; using u64 = uint64_t; class rolling_hash { static constexpr u64 M = (1ULL << 51) * 4011 + 1, M2 = M - 2, R2 = static_cast(-__uint128_t(M) % M); static constexpr u64 MR(__uint128_t t) { u64 r = u64((__uint128_t(u64(t) * M2) * M + t) >> 64); return r < M ? r : r - M; } static constexpr u64 init(__uint128_t x) { return MR(x * R2); } static constexpr u64 mod_mul(__uint128_t x, u64 y) { return MR(x * y); } string s; size_t n; static constexpr u64 b61 = 1734700174076058667UL; vector B, H; public: rolling_hash() {} explicit rolling_hash(const string &_s); u64 calc_hash(size_t l, size_t r) const; // [l, r]. つまり l も r も含む。1-indexed. u64 calc_hash2(size_t l, size_t len) const; // l から len 文字。1-indexed. }; inline rolling_hash::rolling_hash(const string &_s) : s(_s), n(s.size()) { B.resize(n+1); H.resize(n+1); B[0] = init(1); for(size_t i=0; i= M) { H[i+1] -= M; } } } inline u64 rolling_hash::calc_hash(size_t l, size_t r) const { return calc_hash2(l, r-l+1); } inline u64 rolling_hash::calc_hash2(size_t l, size_t len) const { u64 x = H[l+len-1], yz = mod_mul(B[len], H[l-1]); return x < yz ? M - yz + x : x - yz; } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); string s; int m; cin >> s >> m; rolling_hash rh(s); 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); res += mp[rh2.calc_hash(1, ci.size())]; } cout << res << '\n'; return 0; }