Warning: This editorial is probably new and arcane for ones who are not familiar with this field. If you just want to get a quick idea about the solution, you can skip all the proofs (they're wrapped in spoiler tags).
Some symbols: All indices of strings start from zero. xR stands for the reverse of string x. (e.g. 'abc'R = 'cba'), xy stands for concatenation of x and y. (e.g. x = 'a', y = 'b', xy = 'ab'), xa stands for concatenation of a copies of x (e.g. x = 'ab', x2 = 'abab'). x[a, b] stands for the substring of x starting and ending from the a-th and b-th character. (e.g. 'abc'[1, 2] = 'bc')
Border of x: strings with are common prefix & suffix of x. Formally, x has a border of length t (x[0, t - 1]) iff xi = x|x| - t + i ().
Period of x: x has a period of length t iff xi = xi + t (0 ≤ i < |x| - t). When t||x| we also call t a full period. From the formulas it's easy to see x has a period of length t iff x has a border of length |x| - t. ()
Power: x is a power iff the minimum full period of x isn't |x|. e.g. abab is a power.
Lemma 1 (weak periodicity lemma): if p and q are periods of s, p + q ≤ |s|, gcd(p, q) is also a period of s.
ProofSuppose p < q, d = q - p.
If |s| - q ≤ i < |s| - d, si = si - p = si + d.
If 0 ≤ i < |s| - q, si = si + q = si + q - p = si + d.
So q - p is also a period. Using Euclid algorithm we can get gcd(p, q) is a period.
Lemma 2: Let S be the set of period lengths ≤ |s| / 2 of s, if S is non-empty, .
ProofLet min S = v, since v + u ≤ |s|, gcd(v, u) is also a valid period, so gcd(v, u) ≥ v, v|u.
Let border(x) be the longest (not-self) border of x. e.g. border('aba') = 'a', border('ab') = ".
If x is a palindrome, its palindromic prefix and suffix must be its border. Therefore, its (not-self) longest palindromic prefix (suffix) is border(x).
ProofLet |x| = a, x has a border of length b iff xi = xa - b + i (), x has a palindromic prefix of length b iff xi = xb - 1 - i (). Since xi = xa - 1 - i, they are just the same.
If S = pq, p and q are palindromic and non-empty, we call (p, q) a palindromic decomposition of S. If S = pq, p and q are palindromic, q is non-empty (p can be empty) we call (p, q) a non-strict palindromic decomposition of S.
Lemma 3: if S = x1 x2 = y1 y2 = z1 z2, |x1| < |y1| < |z1|, x2, y1, y2, z1 are palindromic and non-empty, then x1 and z2 are also palindromic.
ProofLet z1 = y1 v.
vR is a suffix of y2, also a suffix of x2. So v is a prefix of x2, then x1v is a prefix of z1.
Since y1 is a palindromic prefix of z1, z1 = y1 v, |v| is a period of z1. Since x1v is a prefix, so |v| is also a period of x1 v.
Suppose t be some arbitary large number (you can think of it as ∞), then x1 is a suffix of vt.
Since vR is prefix of z1, x1 is a prefix of (vR)t. So x1R is a suffix of vt, then x1 = x1R, so x1 is palindromic. z2 is palindromic similarly.
Lemma 4: Suppose S has some palindromic decomposition. Let the longest palindromic prefix of S be a, S = ax, longest palindromic suffix of S be b, S = yb. At least one of x and y is palindromic.
ProofIf none of them are palindromic, let S = pq be a valid palindromic decomposition of S, then S = yb = pq = ax, by Lemma 3, contradiction.
Lemma 5: S = p1 q1 = p2 q2 (|p1| < |p2|, p1, q1, p2, q2 are palindromic, q1 and q2 are non-empty), then S is a power.
ProofWe prove this by proving gcd(|p2| - |p1|, |S|) is a period.
Let |S| = n, |p2| - |p1| = t.
Because p1 is a palindromic prefix of p2, t is a period of p2. Similarly t is a period of q1. Since they have a common part of length t (namely S[p1, p2 - 1]), t is a period of S. So t is a period of S.
For , sx = s|p2| - 1 - x = sn - 1 + |p1| - (|p2| - 1 - x) = sn - t + x (first two equations are because p2 and q1 and palindromic). So n - t is also a period of S.
Since t + n - t = n, gcd(t, n - t) = gcd(t, n) is also a period of S. (weak periodicity lemma)
Lemma 6: Let S = p1 q1 = p2 q2 = ... = pt qt be all non-strict palindromic decompositions of S, h be the minimum full period of S. When t ≠ 0, t = |S| / h.
ProofFrom Lemma 5, it's clear that h = |S| iff t = 1. In the following t ≥ 2 is assumed.
Let α = S[0, h - 1], because α is not a power (otherwise s will have smaller full period), α has at most one non-strict palindromic decomposition (from Lemma 5).
Let S = pq be any non-strict palindromic decomposition, then max(|p|, |q|) ≥ h. When |p| ≥ h, α = p[0, h - 1], so , then is palindromic. Similarly is also palindromic. When |q| ≥ h similar arguments can be applied. Therefore, and is a non-strict palindromic decomposition of α.
Therefore, α has a non-strict palindromic decomposition. Let its only non-strict palindromic decomposition be α[0, g - 1] and α[g, h - 1]. Therefore, every pi must satisfy , so t ≤ |s| / h. Also, these all |s| / h decompositions can be obtained.
Lemma 7: Let S = p1 q1 = p2 q2 = ... = pt qt be all non-strict palindromic decompositions of S. (|pi| < |pi + 1|) For every , at least one of pi = border(pi + 1) and qi + 1 = border(qi) is true.
ProofInstead of proving directly, we first introduce a way to compute all decompositions.
Let the longest palindromic prefix of S be a (a ≠ S), S = ax, longest palindromic suffix of S be b (it may be S), S = yb.
If x = b obviously S = ab is the only way to decompose.
If S = pq and p ≠ a, q ≠ b, p and q are palindromic, by Lemma 3 we have x, y are also palindromic.
So if neither x or y is palindromic, then S can't be composed to two palindromes.
If exactly one of x and y is palindromic, it's the only way to decompose S.
If both of them are palindromic, we can then find the second-longest non-self palindromic prefix of S: c. Let S = cz, if z is not palindromic or c = y, then S = ax = yb are the only non-strict palindromic decompositions. Otherwise, we can find all palindromic suffix of |S| whose lengths between |z| and |b|, their prefixes must also be palindromic (using Lemma 3 for ax and cz), then S = ax = cz = ... = yb (other palindromic suffixes and their corresponding prefixes are omitted)
Back to the proof of Lemma 7, the only case we need to prove now is S = ax = yb. Suppose the claim is incorrect, let p = border(a), s = border(y), S = ax = pq = rs = yb, (|a| > |p| > |y|, |a| > |r| > |y|, p and s are palindromic)
Continuing with the proof of Lemma 6, since t = 2, S = α2. If |p| ≥ |α|, , so q would also be palindromic, contradiction. Therefore, |p| < |α| and similarly |s| < |α|. Let α = pq' = r's and the non-strict palindromic decomposition of α be α = βθ. Since α = pq' = βθ = r's, by Lemma 3 q' and r' should also be palindromic, contradiction.
Lemmas are ready, let's start focusing on this problem. A naive idea is to count the number of palindromes in A and in B, and multiply them. This will obviously count a string many times. By Lemma 7, suppose S = xy, to reduce counting, we can check if using border(x) or border(y) to replace x or y can also achieve S. If any of them do, reduce the answer by 1, then we're done.
So for a palindromic string x in A, we want to count strings that are attainable from both x and border(x) and subtract from the answer. Finding x and border(x) themselves can be simply done by the palindromic tree.
Let x = border(x)w, we want to count Ts in B that T = wS and both T and S are palindromic. Since |w| is the shortest period of x, w can't be a power.
If |w| > |S|, w = S + U. S are U are both palindromes. Since w is not a power, it can be decomposed to be two palindromes in at most one way (Lemma 5). We can find that only way (by checking maximal palindromic suffix & prefix) and use hashing to check if it exists in B.
If |w| ≤ |S|, if S is not maximum palindromic suffix of T, w must be a power (Lemma 2), so we only need to check maximum palindromic suffixes (i.e. S = border(T)).
We need to do the similar thing to ys in B, then adding back both attainable from border(x) and border(y). Adding back can be done in a similar manner, or directly use hashing to find all matching w s.
Finding maximal palindromic suffix and prefix of substrings can be done by binary-lifting on two palindromic trees (one and one reversed). Let upi, j be the resulting node after jumping through fail links for 2j steps from node i. While querying maximal palindromic suffix for s[l, r], find the node corresponding to the maximal palindromic suffix of s[1, r] (this can be stored while building palindromic tree). If it fits into s[l, r] we're done. Otherwise, enumerate j from large to small and jump 2j steps (with the help of up) if the result node is still unable to fit into s[l, r], then jump one more step to get the result.