#include using namespace std; template struct MultiPalindromicTree{ private: struct Node{ map link; int link_rev = -1; int suffix_link = -1; // same suffix maximum pal int len; // palindrome length array cnt; // freq of this pair idx; // one of the start pos Node() = default; Node(int len): len(len), cnt{}, idx(-1, -1) {} int succ(const T &c) const { auto it = link.find(c); if(it == link.end()) return -1; return it->second; } }; // find longest P s.t. c + P + c is pal int find_next_pal(int p, int k) const { int pos = int(seq[p].size()) - 1; while(true){ int i = pos - 1 - nodes[k].len; if(i >= 0 && seq[p][i] == seq[p][pos]) return k; k = nodes[k].suffix_link; } } public: vector nodes; array, 2> seq = {}; array suffix_max = {}; MultiPalindromicTree(){ nodes.emplace_back(-1); // odd node nodes.emplace_back(0); // even node nodes[1].suffix_link = 0; } void add(int i, const T &c){ seq[i].push_back(c); int k = find_next_pal(i, suffix_max[i]); // c + P + c is already exists if(int p = nodes[k].succ(c); p != -1){ ++nodes[p].cnt[i]; suffix_max[i] = p; return; } // unique nodes[k].link[c] = suffix_max[i] = int(nodes.size()); int len = nodes[k].len + 2; nodes.emplace_back(len); nodes.back().cnt[i] = 1; nodes.back().idx = {i, int(seq[i].size()) - len}; nodes.back().link_rev = k; if(len == 1) nodes.back().suffix_link = 1; else nodes.back().suffix_link = nodes[find_next_pal(i, nodes[k].suffix_link)].link[c]; } template void add(int i, Iiter first, Iiter last){ for(; first != last; ++first) add(i, *first); } template void add(int i, const Container &c){ add(i, begin(c), end(c)); } // idx of suffix palindromes of node k vector suffix_palindromes(int k) const { vector ret; for(; nodes[k].len > 0; k = nodes[k].suffix_link){ ret.push_back(k); } return ret; } // idx of substring palindromes of node k vector substr_palindroms(int k) const { vector ret, seen(nodes.size()); queue qu; qu.push(k); seen[k] = 1; for(; !qu.empty(); qu.pop()){ int v = qu.front(); ret.push_back(v); for(int u : {nodes[v].suffix_link, nodes[v].link_rev}){ if(!seen[u]) qu.push(u), seen[u] = 1; } } return ret; } // not count "" int count() const { return int(nodes.size()) - 2; } vector> palindromes_frequency() const { int m = int(nodes.size()); vector> freq(m); for(int i = m - 1; i >= 1; --i){ for(int j = 0; j < 2; ++j){ freq[i][j] += nodes[i].cnt[j]; freq[nodes[i].suffix_link][j] += freq[i][j]; } } return freq; } const Node &operator[](int k) const { return nodes[k]; } }; int main() { MultiPalindromicTree mpt; string s, t; cin >> s >> t; mpt.add(0, s); mpt.add(1, t); auto freq = mpt.palindromes_frequency(); int64_t ans = 0; for(int i = 0; i < mpt.count(); ++i){ ans += freq[i + 2][0] * 1ll * freq[i + 2][1]; } cout << ans << "\n"; }