#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#if __cplusplus >= 201103L //#include //#include //#include //#include // //#define cauto const auto& //#else //#endif using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vint; typedef vector > vvint; typedef vector vll, vLL; typedef vector > vvll, vvLL; #define VV(T) vector > template void initvv(vector > &v, int a, int b, const T &t = T()){ v.assign(a, vector(b, t)); } template void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define reep(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) reep((i),0,(n)) #define ALL(v) (v).begin(),(v).end() #define PB push_back #define F first #define S second #define mkp make_pair #define RALL(v) (v).rbegin(),(v).rend() #define DEBUG #ifdef DEBUG #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #else #define dump(x) #define debug(x) #endif #define MOD 1000000007LL #define EPS 1e-8 #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define maxs(x,y) x=max(x,y) #define mins(x,y) x=min(x,y) class charSA{ unsigned char mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; #define tget(i) ( (t[(i)/8]&mask[(i)%8]) ? 1 : 0 ) #define tset(i, b) t[(i)/8]=(b) ? (mask[(i)%8]|t[(i)/8]) : ((~mask[(i)%8])&t[(i)/8]) #define chr(i) (cs==sizeof(int)?((unsigned int*)s)[i]:((unsigned char *)s)[i]) #define isLMS(i) (i>0 && tget(i) && !tget(i-1)) // find the start or end of each bucket void getBuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, sum = 0; for (i = 0; i <= K; i++) bkt[i] = 0; // clear all buckets for (i = 0; i < n; i++) bkt[chr(i)]++; // compute the size of each bucket for (i = 0; i <= K; i++) { sum += bkt[i]; bkt[i] = end ? sum : sum - bkt[i]; } } // compute SAl void induceSAl(unsigned int *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, j; getBuckets(s, bkt, n, K, cs, end); // find starts of buckets for (i = 0; i < n; i++) { j = SA[i] - 1; if (j >= 0 && !tget(j)) SA[bkt[chr(j)]++] = j; } } // compute SAs void induceSAs(unsigned int *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, j; getBuckets(s, bkt, n, K, cs, end); // find ends of buckets for (i = n - 1; i >= 0; i--) { j = SA[i] - 1; if (j >= 0 && tget(j)) SA[--bkt[chr(j)]] = j; } } // find the suffix array SA of s[0..n-1] in {1..K}^n // require s[n-1]=0 (the sentinel!), n>=2 // use a working space (excluding s and SA) of at most 2.25n+O(1) for a constant alphabet void SA_IS(unsigned char *s, int *SA, int n, int K, int cs) { // cout<<"SA_IS "<= 0; i--) tset(i, (chr(i) 0 && (isLMS(pos+d) || isLMS(prev+d))) break; if (diff) { name++; prev = pos; } pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2; SA[n1 + pos] = name - 1; } for (i = n - 1, j = n - 1; i >= n1; i--) if (SA[i] >= 0) SA[j--] = SA[i]; // stage 2: solve the reduced problem // recurse if names are not yet unique int *SA1 = SA, *s1 = SA + n - n1; if (name < n1){ SA_IS((unsigned char*) s1, SA1, n1, name - 1, sizeof(int)); } else{ // generate the suffix array of s1 directly for (i = 0; i < n1; i++) assert(s1[i]>=0),SA1[s1[i]] = i; } // stage 3: induce the result for the original problem // put all left-most S characters into their buckets getBuckets(s, bkt, n, K, cs, true); // find ends of buckets for (i = 1, j = 0; i < n; i++) if (isLMS(i)) s1[j++] = i; // get p1 for (i = 0; i < n1; i++) SA1[i] = s1[SA1[i]]; // get index in s for (i = n1; i < n; i++) SA[i] = -1; // init SA[n1..n-1] for (i = n1 - 1; i >= 0; i--) { j = SA[i]; SA[i] = -1; SA[--bkt[chr(j)]] = j; } induceSAl(t, SA, s, bkt, n, K, cs, false); induceSAs(t, SA, s, bkt, n, K, cs, true); delete[] bkt; delete[] t; } public: // constructor charSA(){ } vector buildCharSA(string &u, int K, int cs = 1){ int n = u.size(); int *sa = new int[n+1]; // integer sequence unsigned char* s = (unsigned char *) u.c_str(); SA_IS(s, sa, n + 1, K, cs); vector ret(n); for(int i = 0; i < n; i++){ ret[i]=sa[i+1]; } delete[] sa; return ret; } }; vector calc_lcp(vector sa, string s) { int n=s.size(),k=0; vector lcp(n,0); vector rank(n,0); for(int i=0; i calc_lcp(const vector &sa, const string &s){ // int n = s.size(); // vector lcp(n); // vector rank(n,0); // for (int i = 1; i < n; i++){ // rank[sa[i-1]] = i; // } // for(int i = 0, h = 0; i < n; i++) { // if(rank[i] < n - 1) { // for (int j = sa[rank[i]]; s[i + h] == s[j + h]; ++h); // lcp[rank[i]] = h; // if (h > 0){ // --h; // } // } // } // lcp[n - 1]=0; // for (int i = 0; i < n; i++){ // if(s[sa[n-1] + i] != s[sa[n-2] + i]) break; // lcp[n - 1]++; // } // return lcp; // } // RMQ pre(O(n)) query O(1) template class RMQ { public: vector data; vector > block; vector sblock; int N; // int lg; // if Range_MAximam_Query -> return data[b] > data[a] ? b : a int argMin(int a, int b) { return data[b] < data[a] ? b : a; } // x の下位 y bit を 0 にする int maskBits(int x, int y) { return (x >> y) << y; } RMQ(){} void init(vector &v) { data = v; N = data.size(); // lg = 32 - __builtin_clz(N); int blockSize = ((N - 1) >> 5) + 1; block.assign(blockSize, vector(32, 0)); for(int i = 0; i < N; i++) { if(i % 32 == 0) block[i >> 5][0] = i; block[i >> 5][0] = argMin(block[i >> 5][0], i); } for(int j = 1; j < block[0].size(); j++) { for(int i = 0; i < block.size(); i++) { block[i][j] = argMin(block[i][j - 1], block[min(i + (1 << (j - 1)), (int)block.size() - 1)][j - 1]); } } sblock.assign(N, 0); vector st(32); int stackSize = 0; for(int i = 0; i < N; i++) { if(i % 32 == 0) stackSize = 0; while(stackSize && i == argMin(i, st[stackSize - 1])) --stackSize; if(stackSize) { int g = st[stackSize - 1]; sblock[i] = sblock[g] | (1 << (g % 32)); } st[stackSize++] = i; } } // min{data[i] : i in [l .. r]} T query(int l, int r) { if(l == r) return data[l]; int l1 = (l >> 5) + 1; int r1 = (r >> 5) - 1; int ret = l; if(l1 <= r1) { // calc sparse table int d = r1 - l1 + 1; if(d <= 2) { ret = argMin(ret, argMin(block[l1][0], block[r1][0])); } else { int lg2 = 32 - __builtin_clz(d) - 1; ret = argMin(ret, argMin(block[l1][lg2], block[r1 - (1 << lg2) + 1][lg2])); } } if(l1 - r1 == 2) { // same block int t = maskBits(sblock[r], l % 32); if(t == 0) { ret = argMin(ret, r); } else { ret = argMin(ret, __builtin_ctz(t) + ((l1 - 1) << 5)); } } else { // other block int t1 = maskBits(sblock[(l1 << 5) - 1], l % 32); if(t1 == 0) { ret = argMin(ret, (l1 << 5) - 1); } else { ret = argMin(ret, __builtin_ctz(t1) + ((l1 - 1) << 5)); } int t2 = sblock[r]; if(t2 == 0) { ret = argMin(ret, r); } else { ret = argMin(ret, __builtin_ctz(t2) + ((r1 + 1) << 5)); } } return data[ret]; } }; // RollingHash rh; string s; int n; RMQ rmq; vint Rank; int LCE(int l, int r){ return rmq.query(min(Rank[l], Rank[r])+1, max(Rank[l], Rank[r])); } static const int MAX_SIZE = 1 << 14; //segment tree のサイズ。 2^17 ≒ 1.3 * 10^5 ll all[2 * MAX_SIZE - 1], part[2 * MAX_SIZE - 1]; // segment tree //区間[a, b)に値xを加算する. void add(int a, int b, ll x, int k = 0, int l = 0, int r = MAX_SIZE) { if (a <= l && r <= b){ //[l, r)が[a, b)に完全に内包されていれば all[k] += x; //[l, r)の全ての区間が持つ値としてxを足す. } else if (l < b && a < r){ //[l, r)と[a, b)が交差していれば part[k] += (min(b, r) - max(a, l)) * x; //交差している分の値を, 部分的な和を持つノードに加算する. add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子でも同じ処理を行う. add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃. } } ll sum(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE) { if (b <= l || r <= a){ //[a, b)と[l, r)が全く交差しない場合 return (0); } else if (a <= l && r <= b){ //完全に内包されていれば return (all[k] * (r - l) + part[k]); } else { //[l, r)と[a, b)が交差していれば ll res; res = (min(b, r) - max(a, l)) * all[k]; //そのノードの全ての要素が持つ値のうち, [a, b)に属すものの分だけを加算する. res += sum(a, b, k * 2 + 1, l, (l + r) / 2); //子ノードで和を求める. res += sum(a, b, k * 2 + 2, (l + r) / 2, r); //〃 return (res); } } bool isPal(string a){ string b = a; reverse(ALL(b)); return a == b; } int func(string a){ int ret = 0; rep(i,a.size()-1){ if(isPal(a.substr(0,i+1))&&isPal(a.substr(i+1))) { ret++; } } return ret; } // int ff(string a){ // int n = a.size(); // rep(i,n){ // rep(j,i){ // for(int k=i+2) // } // } // } set> se; charSA csa; vint sa; vll lcp; void mainmain(){ cin>>s; n = s.size(); string r = s; reverse(ALL(r)); string sr = s+'$'+r; sa = csa.buildCharSA(sr, 256); lcp = calc_lcp(sa, sr); // rep(i,sa.size()){ // cout<F.F,rr=it->F.S,t=it->S; // if(i==5) cout<F.F,rr=it->F.S,t=it->S; // if(i==1) cout<=0;i--){ c[i] += c[i+1]; } ll ans = 0; rep(i,n-2){ ans += b[i] * c[i+2]; } cout << ans << endl; // cout<