#include #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; const long long MOD = 10000000000000099; const long long BASE = 1333; const int MAXN = 5 * 100000; long long POWER[MAXN + 1]; long long mul(long long a, long long b) { return ((__int128_t)a * b) % MOD; } class RollingHash { public: RollingHash(const string& s) : size(s.size()), str(s) { hashed.resize(size + 1); for (int i = 0; i < size; ++i) { hashed[i + 1] = mul(hashed[i], BASE) + (s[i]); hashed[i + 1] %= MOD; } } long long query(int l, int r) { assert(0 <= l && l <= r && r <= size); return (hashed[r] - mul(hashed[l], POWER[r - l]) + MOD) % MOD; } private: string str; vector hashed; int size; }; class Eertree { public: Eertree(const string& s) : str(s), size(s.size()), r1(s), r2(string(s.rbegin(), s.rend())) {} void build() { const int BEGIN = 'A'; // or 'a' const int PALINDROME_SIZE = 2 * size; vector> G(PALINDROME_SIZE); H.resize(PALINDROME_SIZE); W.resize(PALINDROME_SIZE, 0); vector> ptr(27); ptr[26][0] = 0; H[0] = {26, 0}; int free = 1; for (int i = 0; i < size; ++i) { int ID = str[i] - BEGIN; int ok = -1, ng = min(i, size - i - 1) + 1; while (ng - ok > 1) { int x = (ng + ok) >> 1; long long h1 = r1.query(i + 1, i + 1 + x); long long h2 = r2.query(size - i, size - i + x); if (ptr[ID].count(h1) && ptr[ID][h1] >= 0 && h1 == h2) ok = x; else ng = x; } if (ok == -1) { ptr[ID][0] = free; H[free] = {ID, 0}; free++; ok = 0; } int par = ptr[ID][r1.query(i + 1, i + 1 + ok)]; for (int j = ok + 1; j < min(i + 1, size - i); ++j) { if (str[i + j] == str[i - j]) { long long h1 = r1.query(i + 1, i + j + 1); ptr[ID][h1] = free; G[par].push_back(free); H[free] = {ID, h1}; par = free; free++; } else { break; } } W[par] += 1; // Centroid = '' ok = 0; ng = min(i, size - i - 1) + 1; ID = 26; while (ng - ok > 1) { int x = (ng + ok) >> 1; long long h1 = r1.query(i, i + x); long long h2 = r2.query(size - i, size - i + x); if (ptr[ID].count(h1) && ptr[ID][h1] >= 0 && h1 == h2) ok = x; else ng = x; } par = ptr[ID][r1.query(i, i + ok)]; for (int j = ok + 1; j < min(i + 1, size - i + 1); ++j) { if (str[i + j - 1] == str[i - j]) { long long h1 = r1.query(i, i + j); ptr[ID][h1] = free; G[par].push_back(free); H[free] = {ID, h1}; par = free; free++; } else { break; } } W[par] += 1; } function dfs = [&](int v) { for (int nxt : G[v]) { W[v] += dfs(nxt); } return W[v]; }; for (int ID = 0; ID < 27; ++ID) { if (ptr[ID].count(0) && ptr[ID][0] >= 0) dfs(ptr[ID][0]); } W[0] = 0; } vector getW() const { return W; } vector> getH() const { return H; } private: string str; int size; RollingHash r1, r2; vector W; vector> H; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for (int i = 0; i <= MAXN; ++i) { POWER[i] = (i == 0) ? 1 : mul(POWER[i - 1], BASE); } string s, t; cin >> s >> t; Eertree palS(s); Eertree palT(t); palS.build(); palT.build(); vector SW = palS.getW(); vector TW = palT.getW(); vector> SH = palS.getH(); vector> TH = palT.getH(); unordered_map> pair; for (size_t i = 0; i < SW.size(); ++i) { pair[SH[i].first*MOD+SH[i].second][0] += SW[i]; } for (size_t i = 0; i < TW.size(); ++i) { pair[TH[i].first*MOD+TH[i].second][1] += TW[i]; } long long ans = 0; for (const auto& p : pair) { ans += p.second[0] * p.second[1]; } cout << ans << '\n'; return 0; }