#include using namespace std; const long long BASE = 123456789; const long long M30 = ((long long) 1 << 30) - 1; const long long M31 = ((long long) 1 << 31) - 1; const long long MOD = ((long long) 1 << 61) - 1; unsigned long long modulo(unsigned long long x){ unsigned long long xu = x >> 61; unsigned long long xd = x & MOD; unsigned long long res = xu + xd; if (res >= MOD){ res -= MOD; } return res; } unsigned long long mul(unsigned long long a, unsigned long long b){ unsigned long long au = a >> 31; unsigned long long ad = a & M31; unsigned long long bu = b >> 31; unsigned long long bd = b & M31; unsigned long long mid = au * bd + ad * bu; unsigned long long midu = mid >> 30; unsigned long long midd = mid & M30; return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd); } struct rolling_hash{ vector POW, S; rolling_hash(string s){ int N = s.size(); POW.resize(N + 1); POW[0] = 1; for (int i = 0; i < N; i++){ POW[i + 1] = mul(POW[i], BASE); } S.resize(N + 1); S[N] = 0; for (int i = N - 1; i >= 0; i--){ S[i] = modulo(mul(S[i + 1], BASE) + s[i]); } } long long get(int L, int R){ return modulo(S[L] + MOD - mul(S[R], POW[R - L])); } }; vector manacher(string &S){ int N = S.size(); vector ans(N, 0); int i = 0, j = 0; while (i < N){ while (i >= j && i + j < N && S[i - j] == S[i + j]){ j++; } ans[i] = j; int k = 1; while (i >= k && i + k < N && k + ans[i - k] < j){ ans[i + k] = ans[i - k]; k++; } i += k; j -= k; } return ans; } vector suffix_array(const vector &A, int mx){ int N = A.size(); vector sum(mx + 1, 0); for (int i = 0; i < N; i++){ sum[A[i] + 1]++; } for (int i = 0; i < mx; i++){ sum[i + 1] += sum[i]; } vector is_s(N); is_s[N - 1] = false; for (int i = N - 2; i >= 0; i--){ is_s[i] = A[i] < A[i + 1] || A[i] == A[i + 1] && is_s[i + 1]; } vector id(N, -1); vector pos; int M = 0; for (int i = 1; i < N; i++){ if (is_s[i] && !is_s[i - 1]){ id[i] = M; pos.push_back(i); M++; } } vector sa(N); auto induce = [&](vector& lms){ sa = vector(N, -1); vector used(N, false); vector p(mx); vector p2(mx); for (int i = 0; i < mx; i++){ p[i] = sum[i + 1] - 1; p2[i] = sum[i]; } for (int i = M - 1; i >= 0; i--){ sa[p[A[lms[i]]]] = lms[i]; p[A[lms[i]]]--; used[lms[i]] = true; } sa[p2[A[N - 1]]] = N - 1; p2[A[N - 1]]++; used[N - 1] = true; for (int i = 0; i < N; i++){ if (sa[i] > 0){ if (!is_s[sa[i] - 1] && !used[sa[i] - 1]){ sa[p2[A[sa[i] - 1]]] = sa[i] - 1; p2[A[sa[i] - 1]]++; used[sa[i] - 1] = true; } } } for (int i = 0; i < N; i++){ if (sa[i] != -1){ if (id[sa[i]] != -1){ used[sa[i]] = false; sa[i] = -1; } } } for (int i = 0; i < mx; i++){ p[i] = sum[i + 1] - 1; } for (int i = N - 1; i >= 0; i--){ if (sa[i] > 0){ if (is_s[sa[i] - 1] && !used[sa[i] - 1]){ sa[p[A[sa[i] - 1]]] = sa[i] - 1; p[A[sa[i] - 1]]--; used[sa[i] - 1] = true; } } } }; induce(pos); if (M == 0){ return sa; } vector lms; for (int i = 0; i < N; i++){ if (id[sa[i]] != -1){ lms.push_back(sa[i]); } } vector c(M); c[0] = 0; for (int i = 0; i < M - 1; i++){ c[i + 1] = c[i]; int x = lms[i]; int y = lms[i + 1]; bool ok = true; while (x < N && y < N){ if (A[x] != A[y]){ ok = false; break; } x++; y++; if (id[x] != -1){ if (id[y] == -1){ ok = false; } break; } } if (x == N || y == N){ ok = false; } if (!ok){ c[i + 1]++; } } vector rec(M); for (int i = 0; i < M; i++){ rec[id[lms[i]]] = c[i]; } vector sa2 = suffix_array(rec, c[M - 1] + 1); vector pos2(M); for (int i = 0; i < M; i++){ pos2[i] = pos[sa2[i]]; } induce(pos2); return sa; } vector suffix_array(const string &S){ int N = S.size(); vector A(N); for (int i = 0; i < N; i++){ A[i] = S[i]; } return suffix_array(A, 256); } vector lcp_array(string &S, vector &SA){ int N = S.size(); vector rank(N); for (int i = 0; i < N; i++){ rank[SA[i]] = i; } vector lcp(N - 1, 0); int h = 0; for (int i = 0; i < N; i++){ if (rank[i] > 0){ int prev = SA[rank[i] - 1]; if (h > 0){ h--; } while (i + h < N && prev + h < N){ if (S[i + h] != S[prev + h]){ break; } h++; } lcp[rank[i] - 1] = h; } } return lcp; } template struct sparse_table{ vector> ST; sparse_table(vector &A){ int N = A.size(); int LOG = 32 - __builtin_clz(N); ST = vector>(LOG, vector(N)); for (int i = 0; i < N; i++){ ST[0][i] = A[i]; } for (int i = 0; i < LOG - 1; i++){ for (int j = 0; j < N - (1 << i); j++){ ST[i + 1][j] = min(ST[i][j], ST[i][j + (1 << i)]); } } } T range_min(int L, int R){ int d = 31 - __builtin_clz(R - L); return min(ST[d][L], ST[d][R - (1 << d)]); } }; unordered_map solve(string S){ int N = S.size(); string T = "$"; for (int i = 0; i < N; i++){ T += S[i]; T += '$'; } vector A = manacher(T); vector SA = suffix_array(S); vector LCP = lcp_array(S, SA); sparse_table ST(LCP); rolling_hash RH(S); vector rank(N); for (int i = 0; i < N; i++){ rank[SA[i]] = i; } unordered_map mp; for (int i = 1; i < N * 2; i++){ int l = (i - A[i] + 2) / 2, r = (i + A[i] - 1) / 2; while (l < r){ unsigned long long hash = RH.get(l, r); if (mp.count(hash) == 1){ break; } int tv1 = rank[l], fv1 = N; while (fv1 - tv1 > 1){ int mid = (tv1 + fv1) / 2; if (ST.range_min(rank[l], mid) >= r - l){ tv1 = mid; } else { fv1 = mid; } } int tv2 = rank[l], fv2 = -1; while (tv2 - fv2 > 1){ int mid = (tv2 + fv2) / 2; if (ST.range_min(mid, rank[l]) >= r - l){ tv2 = mid; } else { fv2 = mid; } } mp[hash] = tv1 - tv2 + 1; l++; r--; } } return mp; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); string S; cin >> S; string T; cin >> T; unordered_map A = solve(S); unordered_map B = solve(T); long long ans = 0; for (auto P : A){ if (B.count(P.first) == 1){ ans += (long long) P.second * B[P.first]; } } cout << ans << endl; }