#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; const ll t = 999999937; const ll m = 1000000009; const 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); vector> used(n+1); vector> edges; //odd { vector c; manacher(s, c); rep(i, n) { int le = i + 1 - c[i]; int ri = i - 1 + c[i]; int len = ri - le + 1; P cur = rs.calc(le, ri - le + 1); if (used[len].find(cur) != used[len].end()) { used[len][cur]++; continue; } used[len][cur]++; while (le + 1 <= ri - 1) { le++; ri--; len -= 2; P nex = rs.calc(le, ri - le + 1); edges.push_back({ cur,nex }); if (used[len].find(nex) != used[len].end())break; used[len][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; int len = ri - le + 1; P cur = rs.calc(le, ri - le + 1); if (used[len].find(cur) != used[len].end()) { used[len][cur]++; continue; } used[len][cur]++; while (le + 1 <= ri - 1) { le++; ri--; len -= 2; P nex = rs.calc(le, ri - le + 1); edges.push_back({ cur,nex }); if (used[len].find(nex) != used[len].end())break; used[len][nex] = 0; cur = nex; } } } vector> res; rep(i, n + 1) { for (pair p : used[i]) { res.push_back(p); } } sort(all(res)); vector cnt(res.size()); vector nex(res.size(), -1); for (pair p : edges) { int l = lower_bound(all(res), pair{ p.first,-1 }) - res.begin(); int r = lower_bound(all(res), pair{p.second, -1}) - res.begin(); nex[l] = r; cnt[r]++; } queue q; rep(i, res.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]; res[to].second += res[id].second; cnt[to]--; if (cnt[to] == 0) { q.push(to); } } } return res; } void solve() { string s, t; cin >> s >> t; vector> dps = ps(s), dpt = ps(t); 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; }