Palindrome Partition
Contest: Codeforces Round 873 (Div. 1)
Difficulty rating: 2600
Tags: binary search, brute force, data structures, dp, hashing, strings

A substring is a continuous and non-empty segment of letters from a given string, without any reorders.

An even palindrome is a string that reads the same backward as forward and has an even length. For example, strings "zz", "abba", "abccba" are even palindromes, but strings "codeforces", "reality", "aba", "c" are not.

A beautiful string is an even palindrome or a string that can be partitioned into some smaller even palindromes.

You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. Count the number of beautiful substrings of $$$s$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5\cdot 10^5$$$).

The second line of each test case contains a string $$$s$$$. String $$$s$$$ consists of only lowercase Latin letters and has a length of $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output format:
For each test case print the number of beautiful substrings.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the beautiful substrings are "abaaba", "baab", "aa".

In the last test case, the beautiful substrings are "aa" (counted twice), "abba", "bb", "bbaa", "abbaaa".

Example input:
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa

Example output:
3
0
1
0
14
6

Editorial:
For the simplicity of the solution, we will abbreviate even palindrome as evp.
Lemma: Consider a beautiful string $$$t$$$, we can find the **unique maximal** partition for it by greedily choosing the smallest possible evp in each step from the left. Here maximal means maximum number of parts.
Proof: Suppose $$$t[0..l)$$$ is smallest prefix which is an evp and $$$t[0..r)$$$ is the first part in the partition of $$$t$$$, here $$$t[l..r)$$$ mean substring $$$t_l t_{l+1}\ldots t_{r-1}$$$. We consider two cases:
- $$$2l\le r$$$: In this case, it is clear that $$$t[0..l)$$$, $$$t[l..r - l)$$$ and $$$t[r-l..r)$$$ are evps, so we can replace $$$t[0..r)$$$ with them.

- $$$2l>r$$$: In this case, due to the fact that $$$t[r-l..l)$$$ and $$$t[0..l)$$$ are evps, $$$t[0..2l-r)$$$ is also an evp, which contradicts to above assumption that $$$t[0..l)$$$ is the smallest.

We can use dynamic programming to solve this problem. Let $$$dp_i$$$ be the number of beautiful substrings starting at $$$i$$$. For all $$$i$$$ from $$$n-1$$$ to $$$0$$$, if there are such $$$next_i$$$ satisfying $$$s[i..next_i)$$$ is the smallest evp beginning at $$$i$$$, then $$$dp_i=dp_{next_i}+1$$$, otherwise $$$dp_i=0$$$. The answer will be the sum of $$$dp_i$$$ from $$$0$$$ to $$$n-1$$$.
To calculate the $$$next$$$ array, first, we use Manacher algorithm or hashing to find the maximum $$$pal_i$$$ satisfying $$$s[i-pal_i..i+pal_i)$$$ is an evp for each $$$i$$$. Then for all $$$0\le i< n$$$, $$$next_i=2j-i$$$ where $$$j$$$ is smallest position such that $$$i<j$$$ and $$$j-pal_j\le i$$$. The time complexity is $$$\mathcal{O}(n \log{n})$$$.