#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; } } vector> ps(string &s) { int n = s.size(); rolling_hash rs(s); map used; vector> edges; //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); bool pass = false; if (used.find(cur) != used.end())pass = true; used[cur]++; if (pass)continue; while (le + 1 <= ri - 1) { le++; ri--; P nex = rs.calc(le, ri - le + 1); edges.push_back({ cur,nex }); if (used.find(nex) != used.end())break; used[nex] = 0; 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); bool pass = false; if (used.find(cur) != used.end())pass = true; used[cur]++; if (pass)continue; while (le + 1 <= ri - 1) { le++; ri--; P nex = rs.calc(le, ri - le + 1); edges.push_back({ cur,nex }); if (used.find(nex) != used.end())break; used[nex] = 0; cur = nex; } } } vector

exis; vector dp; for (pair p : used) { exis.push_back(p.first); dp.push_back(p.second); } vector cnt(exis.size()); vector nex(exis.size(), -1); sort(all(edges)); int loc = 0; for (pair p : edges){ while (exis[loc]< p.first)loc++; int l = loc; int r = lower_bound(all(exis), p.second) - exis.begin(); nex[l] = r; cnt[r]++; } queue q; rep(i, exis.size())if (cnt[i] == 0)q.push(i); while (!q.empty()) { int id = q.front(); q.pop(); if (nex[id] >= 0) { int to = nex[id]; dp[to] += dp[id]; cnt[to]--; if (cnt[to] == 0) { q.push(to); } } } vector> res; rep(i, exis.size()) { res.push_back({ exis[i],dp[i] }); } return res; } void solve() { string s, t; cin >> s >> t; vector> dps = ps(s), dpt = ps(t); /*for (pair p: dps) { cout << p.first.first << " " << p.first.second << " " << p.second << "\n"; } for (pair p : dpt) { cout << p.first.first << " " << p.first.second << " " << p.second << "\n"; }*/ ll ans = 0; int id1 = 0, id2 = 0; while (id1 < dps.size() && id2 < dpt.size()) { P mi = min(dps[id1].first, dpt[id2].first); ll s1 = 0, s2 = 0; while (id1 < dps.size() && dps[id1].first == mi) { s1 += dps[id1].second; id1++; } while (id2 < dpt.size() && dpt[id2].first == mi) { s2 += dpt[id2].second; id2++; } ans += s1 * s2; } 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; }