Palindromic Magic
Contest: Avito Cool Challenge 2018
Difficulty rating: 3500
Tags: data structures, hashing, strings

After learning some fancy algorithms about palindromes, Chouti found palindromes very interesting, so he wants to challenge you with this problem.

Chouti has got two strings $$$A$$$ and $$$B$$$. Since he likes palindromes, he would like to pick $$$a$$$ as some non-empty palindromic substring of $$$A$$$ and $$$b$$$ as some non-empty palindromic substring of $$$B$$$. Concatenating them, he will get string $$$ab$$$.

Chouti thinks strings he could get this way are interesting, so he wants to know how many different strings he can get.

Input format:
The first line contains a single string $$$A$$$ ($$$1 \le |A| \le 2 \cdot 10^5$$$).

The second line contains a single string $$$B$$$ ($$$1 \le |B| \le 2 \cdot 10^5$$$).

Strings $$$A$$$ and $$$B$$$ contain only lowercase English letters.

Output format:
The first and only line should contain a single integer — the number of possible strings.

Constraints:
Time limit: 2.5 s
Memory limit: 1024.0 MB

Note:
In the first example, attainable strings are

- "a" + "a" = "aa",
- "aa" + "a" = "aaa",
- "aa" + "aba" = "aaaba",
- "aa" + "b" = "aab",
- "a" + "aba" = "aaba",
- "a" + "b" = "ab".

In the second example, attainable strings are "aa", "aaa", "aaaa", "aaaba", "aab", "aaba", "ab", "abaa", "abaaa", "abaaba", "abab", "ba", "baa", "baba", "bb".

Notice that though "a"+"aa"="aa"+"a"="aaa", "aaa" will only be counted once.

Example input:
aa
aba

Example output:
6

Example input:
aaba
abaa

Example output:
15

Editorial:
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. $$$x^R$$$ 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'$$$), $$$x^a$$$ stands for concatenation of $$$a$$$ copies of $$$x$$$ (e.g. $$$x='ab'$$$, $$$x^2='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 $$$x_i=x_{|x|-t+i}$$$ ($$$i \in [0,t-1]$$$).
Period of $$$x$$$: $$$x$$$ has a period of length $$$t$$$ iff $$$x_i=x_{i+t}$$$ ($$$0 \leq 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$$$. ($$$t \in [1,|x|]$$$)
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\leq |s|$$$, $$$gcd(p,q)$$$ is also a period of $$$s$$$.
[Proof]
Suppose $$$p<q, d=q-p$$$.
If $$$|s|-q \leq i <|s|-d$$$, $$$s_i=s_{i-p}=s_{i+d}$$$.
If $$$0 \leq i<|s|-q$$$, $$$s_i=s_{i+q}=s_{i+q-p}=s_{i+d}$$$.
So $$$q-p$$$ is also a period. Using Euclid algorithm we can get $$$gcd(p,q)$$$ is a period.
[/Proof]
Lemma 2: Let $$$S$$$ be the set of period lengths $$$\leq |s|/2$$$ of $$$s$$$, if $$$S$$$ is non-empty, $$$\forall u \in S, \min S|u$$$.
[Proof]
Let $$$\min S=v$$$, since $$$v+u \leq |s|$$$, $$$gcd(v,u)$$$ is also a valid period, so $$$gcd(v,u) \geq v$$$, $$$v|u$$$.
[/Proof]
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)$$$.
[Proof]
Let $$$|x|=a$$$, $$$x$$$ has a border of length $$$b$$$ iff $$$x_i=x_{a-b+i}$$$ ($$$i \in [0,b-1]$$$), $$$x$$$ has a palindromic prefix of length $$$b$$$ iff $$$x_i=x_{b-1-i}$$$ ($$$i \in [0,b-1]$$$). Since $$$x_i=x_{a-1-i}$$$, they are just the same.
[/Proof]
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$$$.
Let's begin the part of palindromic decomposition with a lovely lemma. Lemma 3: if $$$S=x_1x_2=y_1y_2=z_1z_2$$$, $$$|x_1|<|y_1|<|z_1|$$$, $$$x_2, y_1, y_2, z_1$$$ are palindromic and non-empty, then $$$x_1$$$ and $$$z_2$$$ are also palindromic.
[Proof]
Let $$$z_1=y_1v$$$.
$$$v^R$$$ is a suffix of $$$y_2$$$, also a suffix of $$$x_2$$$. So $$$v$$$ is a prefix of $$$x_2$$$, then $$$x_1v$$$ is a prefix of $$$z_1$$$.
Since $$$y_1$$$ is a palindromic prefix of $$$z_1$$$, $$$z_1=y_1v$$$, $$$|v|$$$ is a period of $$$z_1$$$. Since $$$x_1v$$$ is a prefix, so $$$|v|$$$ is also a period of $$$x_1v$$$.
Suppose $$$t$$$ be some arbitary large number (you can think of it as $$$\infty$$$), then $$$x_1$$$ is a suffix of $$$v^t$$$.
Since $$$v^R$$$ is prefix of $$$z_1$$$, $$$x_1$$$ is a prefix of $$$(v^R)^t$$$. So $$$x_1^R$$$ is a suffix of $$$v^t$$$, then $$$x_1=x_1^R$$$, so $$$x_1$$$ is palindromic. $$$z_2$$$ is palindromic similarly.
[/Proof]
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.
[Proof]
If none of them are palindromic, let $$$S=pq$$$ be a valid palindromic decomposition of $$$S$$$, then $$$S=yb=pq=ax$$$, by Lemma 3, contradiction.
[/Proof]
Lemma 5: $$$S=p_1q_1=p_2q_2$$$ ($$$|p_1|<|p_2|$$$, $$$p_1,q_1,p_2,q_2$$$ are palindromic, $$$q_1$$$ and $$$q_2$$$ are non-empty), then $$$S$$$ is a power.
[Proof]
We prove this by proving $$$gcd(|p_2|-|p_1|,|S|)$$$ is a period.
Let $$$|S|=n$$$, $$$|p_2|-|p_1|=t$$$.
Because $$$p_1$$$ is a palindromic prefix of $$$p_2$$$, $$$t$$$ is a period of $$$p_2$$$. Similarly $$$t$$$ is a period of $$$q_1$$$. Since they have a common part of length $$$t$$$ (namely $$$S[p_1,p_2-1]$$$), $$$t$$$ is a period of $$$S$$$. So $$$t$$$ is a period of $$$S$$$.
For $$$x \in [0,t)$$$, $$$s_x=s_{|p_2|-1-x}=s_{n-1+|p_1|-(|p_2|-1-x)}=s_{n-t+x}$$$ (first two equations are because $$$p_2$$$ and $$$q_1$$$ 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)
[/Proof]
Lemma 6: Let $$$S=p_1q_1=p_2q_2=...=p_tq_t$$$ be all non-strict palindromic decompositions of $$$S$$$, $$$h$$$ be the minimum full period of $$$S$$$. When $$$t \neq 0$$$, $$$t=|S|/h$$$.
[Proof]
From Lemma 5, it's clear that $$$h=|S|$$$ iff $$$t=1$$$. In the following $$$t \geq 2$$$ is assumed.
Let $$$\alpha=S[0,h-1]$$$, because $$$\alpha$$$ is not a power (otherwise $$$s$$$ will have smaller full period), $$$\alpha$$$ has at most one non-strict palindromic decomposition (from Lemma 5).
Let $$$S=pq$$$ be any non-strict palindromic decomposition, then $$$max(|p|,|q|) \geq h$$$. When $$$|p| \geq h$$$, $$$\alpha[0,|p| \bmod h-1]=p[0,|p| \bmod h-1]=p^R[0,|p|\bmod h-1]=\alpha^R[0,|p| \bmod h-1]$$$, then $$$\alpha[0,|p| \bmod h-1]$$$ is palindromic. Similarly $$$\alpha[|p| \bmod h,h-1]$$$ is also palindromic. When $$$|q| \geq h$$$ similar arguments can be applied. Therefore, $$$\alpha[0,|p| \bmod h-1]$$$ and $$$\alpha[|p| \bmod h,h-1]$$$ is a non-strict palindromic decomposition of $$$\alpha$$$.
Therefore, $$$\alpha$$$ has a non-strict palindromic decomposition. Let its only non-strict palindromic decomposition be $$$\alpha[0,g-1]$$$ and $$$\alpha[g,h-1]$$$. Therefore, every $$$p_i$$$ must satisfy $$$p_i \bmod h=g$$$, so $$$t \leq |s|/h$$$. Also, these all $$$|s|/h$$$ decompositions can be obtained.
[/Proof]
Lemma 7: Let $$$S=p_1q_1=p_2q_2=...=p_tq_t$$$ be all non-strict palindromic decompositions of $$$S$$$. ($$$|p_i|<|p_{i+1}|$$$) For every $$$i \in [1,t-1]$$$, at least one of $$$p_i=border(p_{i+1})$$$ and $$$q_{i+1}=border(q_i)$$$ is true.
[Proof]
Instead of proving directly, we first introduce a way to compute all decompositions.
Let the longest not-self palindromic prefix of $$$S$$$ be $$$a$$$ $$$(a \neq S)$$$, $$$S=ax$$$, longest palindromic suffix of $$$S$$$ be $$$b$$$, $$$S=yb$$$.
If $$$x=b$$$ obviously $$$S=ab$$$ is the only way to decompose.
If $$$S=pq$$$ and $$$p \neq a, q \neq 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=\alpha^2$$$. If $$$|p| \geq |\alpha|$$$, $$$q=x[|p|\bmod h,h-1]$$$, so by the proof of Lemma 6, $$$q$$$ would also be palindromic, contradiction. Therefore, $$$|p|<|\alpha|$$$ and $$$|s|<|\alpha|$$$. Let $$$\alpha=pq'=r's$$$. Since $$$\alpha=pq'=ab=r's$$$, by Lemma 3 $$$q'$$$ and $$$r'$$$ should also be palindromic, contradiction.
[/Proof]
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 $$$T$$$s 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| \leq |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 $$$y$$$s 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 $$$up_{i,j}$$$ be the resulting node after jumping through fail links for $$$2^j$$$ 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 $$$2^j$$$ 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.