#include #include #include using namespace std; typedef long long ll; struct Node { int cnt; Node* child[26]; Node():cnt(0){ memset(child, 0, sizeof(child)); } void add(int n, int cnt){ if(child[n] == NULL){ child[n] = new Node; } child[n]->cnt += cnt; } }; void myfree(Node* a){ if(a == NULL)return; for(int i=0;i<26;i++)myfree(a->child[i]); delete a; } ll count(Node* a, Node* b){ if(a == NULL || b == NULL){ return 0; } ll res = a->cnt * b->cnt; for(int i=0;i<26;i++){ res += count(a->child[i], b->child[i]); } return res; } Node* builder(const vector& S, bool odd){ const int N = S.size(); Node *root = new Node; for(int i=0;iadd(S[i], len-l+1); r = r->child[S[i]]; } if(l == len){ int s = i - 1; int t = j; while(s >= 0 && t < N && S[s] == S[t]){ r->add(S[s], 1); r = r->child[S[s]]; --s; ++t; } } i = j; } return root; } vector conv(const string &S){ vector res(S.size()); for(int i=0;i> S >> T; vector vs = conv(S), vt = conv(T); Node *ns, *nt; ll res = 0; ns = builder(vs, true); nt = builder(vt, true); res += count(ns, nt); myfree(ns); myfree(nt); ns = builder(vs, false); nt = builder(vt, false); res += count(ns, nt); myfree(ns); myfree(nt); cout << res << endl; return 0; }