#include #include #include using namespace std; struct eertree{ eertree(string &s){ push(s); } struct node{ int nxt[26] = { 0, }; int len = 0, suf = 0, occur = 0; }; vector trie; int size, maxSuf; void push(string &str){ trie.clear(); trie.resize(3); size = 2; trie[1].len = -1, trie[1].suf = 1; trie[2].len = +0, trie[2].suf = 1; maxSuf = 2; for (int pos = 0; pos < str.length(); pos++) { int cur = maxSuf, len = 0, sym = str[pos] - 'A'; while (1){ len = trie[cur].len; if (pos - len - 1 >= 0 && str[pos - len - 1] == str[pos]) break; cur = trie[cur].suf; } if (trie[cur].nxt[sym]){ maxSuf = trie[cur].nxt[sym]; } else{ maxSuf = ++size; trie.push_back(node()); trie[size].len = trie[cur].len + 2; trie[cur].nxt[sym] = size; if (trie[size].len == 1){ trie[size].suf = 2; } else{ while (1){ cur = trie[cur].suf; len = trie[cur].len; if (pos - len - 1 >= 0 && str[pos - len - 1] == str[pos]){ trie[size].suf = trie[cur].nxt[sym]; break; } } } } trie[maxSuf].occur++; } for (int i = size; i >= 3; i--){ int suf = trie[i].suf; if (suf >= 3){ trie[suf].occur += trie[i].occur; } } } }; long long inter(eertree& a, eertree& b, int i, int j) { long long res = (long long)a.trie[i].occur * b.trie[j].occur; for (int sym = 0; sym < 26; sym++){ int nxtI = a.trie[i].nxt[sym]; int nxtJ = b.trie[j].nxt[sym]; if (nxtI && nxtJ){ res += inter(a, b, nxtI, nxtJ); } } return res; } int main() { string s, t; cin >> s >> t; eertree p(s), q(t); cout << inter(p, q, 1, 1) + inter(p, q, 2, 2); return 0; }