#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //#define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; const ll mod = 786433; const ll INF = mod * mod; typedef pairP; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) #define all(v) (v).begin(),(v).end() typedef pair LP; typedef long double ld; typedef pair LDP; const ld eps = 1e-12; const ld pi = acos(-1.0); ll mod_pow(ll x, ll n, ll m = mod) { ll res = 1; while (n > 0) { if (n & 1)res = res * x%m; x = x * x%m; n >>= 1; } return res; } struct rolling_hash { private: int sz; vector node; vector r; ll t = 999999937; ll m = 1000000009; ll m2 = 1000000007; ll invt, invt2; public: rolling_hash(const string &s) { int n = s.length(); sz = n; node.resize(n + 1); r.resize(n + 1); node[0] = { 0,0 }; invt = mod_pow(t, m - 2, m); invt2 = mod_pow(t, m2 - 2, m2); ll a = 1; ll a2 = 1; rep(i, n) { //r[i] = a; int z = s[i] - 'a'; node[i + 1].first = node[i].first + a * z; node[i + 1].first %= m; node[i + 1].second = node[i].second + a2 * z; node[i + 1].second %= m2; a = a * t%m; a2 = a2 * t%m2; } a = 1; a2 = 1; rep(i, n) { r[i].first = a; a = invt * a%m; r[i].second = a2; a2 = invt2 * a2%m2; } } P calc(int le, int len) { LP ret = { node[le + len].first - node[le].first,node[le + len].second - node[le].second }; if (ret.first < 0)ret.first += m; if (ret.second < 0)ret.second += m2; ret.first = ret.first*r[le].first % m; ret.second = ret.second*r[le].second % m2; return ret; } }; void manacher(const string &s, vector &r) { r.resize(s.size()); int i = 0, j = 0; while (i < s.size()) { while (i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j])++j; r[i] = j; int k = 1; while (i - k >= 0 && i + k < s.size() && k + r[i - k] < j)r[i + k] = r[i - k], ++k; i += k; j -= k; } } map ps(string &s) { int n = s.size(); rolling_hash rs(s); map used; map next; map dp; //odd { vector c; manacher(s, c); rep(i, n) { int le = i + 1 - c[i]; int ri = i - 1 + c[i]; P cur = rs.calc(le, ri - le + 1); dp[cur]++; if(used[cur])continue; used[cur] = true; while (le + 1 <= ri - 1) { le++; ri--; P nex = rs.calc(le, ri - le + 1); next[cur] = nex; if (used[nex])break; used[nex] = true; cur = nex; } } } //even { string ori; ori.push_back('#'); rep(i, n) { ori.push_back(s[i]); ori.push_back('#'); } vector c; manacher(ori, c); rep(i, n) { int le = i - c[2 * i] / 2; int ri = i - 1 + c[2 * i] / 2; if (le > ri)continue; P cur = rs.calc(le, ri - le + 1); dp[cur]++; if(used[cur])continue; used[cur] = true; while (le + 1 <= ri - 1) { le++; ri--; P nex = rs.calc(le, ri - le + 1); next[cur] = nex; if (used[nex])break; used[nex] = true; cur = nex; } } } queue

q; map cnt; for (pair p : used) { if (next.find(p.first) != next.end()) { cnt[next[p.first]]++; } } for (pair p : used) { if (cnt[p.first] == 0) { q.push(p.first); } } while (!q.empty()) { P p = q.front(); q.pop(); if (next.find(p) != next.end()) { P to = next[p]; dp[to] += dp[p]; cnt[to]--; if (cnt[to] == 0) { q.push(to); } } } return dp; } void solve() { string s, t; cin >> s >> t; map dps = ps(s), dpt = ps(t); ll ans = 0; for (pair p : dps) { ans += p.second*dpt[p.first]; } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(7); //init_f(); //init(); //experi(); //int t; cin >> t; rep(i, t)solve(); solve(); //stop return 0; }