#include using namespace std; struct Node { map link; int suffix_link; int len; int count; }; struct PalindromicTree { vector c; string s; int active_idx; Node& create_node() { c.emplace_back(); Node& ret = c.back(); ret.count = 0; return ret; } int find_prev_palindrome_idx(int node_id) { const int pos = int(s.size() - 1); while (true) { const int opposite_side_idx = pos - 1 - c[node_id].len; if (opposite_side_idx >= 0 && s[opposite_side_idx] == s.back()) { break; } node_id = c[node_id].suffix_link; } return node_id; } PalindromicTree() { Node& size_m1 = create_node(); size_m1.suffix_link = 0; size_m1.len = -1; Node& size_0 = create_node(); size_0.suffix_link = 0; size_0.len = 0; active_idx = 0; } void add(char ch) { s.push_back(ch); const int a = find_prev_palindrome_idx(active_idx); auto result = (c[a].link.count(ch) > 0); if (result) { active_idx = c[a].link[ch]; c[active_idx].count++; return; } else { c[a].link[ch] = c.size(); active_idx = c.size(); } Node& new_node = create_node(); new_node.count = 1; new_node.len = c[a].len + 2; if (new_node.len == 1) { new_node.suffix_link = 1; } else { const int b = find_prev_palindrome_idx(c[a].suffix_link); new_node.suffix_link = c[b].link[ch]; } } vector build_frequency() { vector freq(c.size()); for (int i = (int) c.size() - 1; i > 0; i--) { freq[i] += c[i].count; freq[c[i].suffix_link] += freq[i]; } return freq; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s, t; cin >> s >> t; int n = s.size(), m = t.size(); string st = s + ",." + t; PalindromicTree pt; for (int i = 0; i < n; i++) { pt.add(st[i]); } auto freq = pt.build_frequency(); for (int i = n; i < n + m + 2; i++) { pt.add(st[i]); } auto freq2 = pt.build_frequency(); long long ans = 0; for (int i = 2; i < (int) freq.size(); i++) { ans += (long long) (freq2[i] - freq[i]) * freq[i]; } cout << ans << '\n'; }