#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, H; // b[2][s.size()+1], H[2][s.size()+1] 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) { b.resize(2); H.resize(2); 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, t; cin >> s; int n = s.size(); t = s; reverse(begin(t), end(t)); rolling_hash rhs(s, mods, bases), rht(t, mods, bases); int cnt = 0; int i1 = 1; for(int j1=i1; j1<=n; ++j1) { // P1 if(rhs.calc_hash(i1, j1) != rht.calc_hash(n+1-j1, n+1-i1)) { continue; } int i2 = j1 + 1; for(int j2=i2; j2<=n; ++j2) { // P2 if(rhs.calc_hash(i2, j2) != rht.calc_hash(n+1-j2, n+1-i2)) { continue; } for(int i3=j2+2; i3<=n; ++i3) { // +2 int j3 = n; if(rhs.calc_hash(i3, j3) != rht.calc_hash(n+1-j3, n+1-i3)) { continue; } ++cnt; } } } printf("%d\n", cnt); return 0; }