310405: CF1828E. Palindrome Partition
Description
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$.
InputEach 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$.
OutputFor each test case print the number of beautiful substrings.
ExampleInput6 6 abaaba 1 a 2 aa 6 abcdef 12 accabccbacca 6 abbaaaOutput
3 0 1 0 14 6Note
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".
Input
Output
E. 回文划分
一个“子串”是指一个给定字符串中连续且非空的字母片段，不进行任何重排。
一个“偶数长度的回文”是指一个从后往前读和从前往后读都相同的字符串，并且长度为偶数。例如，字符串 "zz"、"abba"、"abccba" 都是偶数长度的回文，但是字符串 "codeforces"、"reality"、"aba"、"c" 不是。
一个“美丽字符串”要么是一个偶数长度的回文，要么是可以被划分为一些更小的偶数长度回文的字符串。
给你一个由 n 个小写拉丁字母组成的字符串 s，计算 s 的“美丽子串”的数量。
输入输出数据格式：
输入：
每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 ≤ t ≤ 10^4)。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 5·10^5)。
每个测试用例的第二行包含一个字符串 s。字符串 s 只包含小写拉丁字母，长度为 n。
保证所有测试用例的 n 之和不超过 5·10^5。
输出：
对于每个测试用例，输出美丽子串的数量。
示例：
输入：
```
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
```
输出：
```
3
0
1
0
14
6
```
注意：
在第一个测试用例中，美丽子串有 "abaaba"、"baab"、"aa"。
在最后一个测试用例中，美丽子串有 "aa"（计算两次）、"abba"、"bb"、"bbaa"、"abbaaa"。题目大意： E. 回文划分 一个“子串”是指一个给定字符串中连续且非空的字母片段，不进行任何重排。 一个“偶数长度的回文”是指一个从后往前读和从前往后读都相同的字符串，并且长度为偶数。例如，字符串 "zz"、"abba"、"abccba" 都是偶数长度的回文，但是字符串 "codeforces"、"reality"、"aba"、"c" 不是。 一个“美丽字符串”要么是一个偶数长度的回文，要么是可以被划分为一些更小的偶数长度回文的字符串。 给你一个由 n 个小写拉丁字母组成的字符串 s，计算 s 的“美丽子串”的数量。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 ≤ t ≤ 10^4)。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 5·10^5)。 每个测试用例的第二行包含一个字符串 s。字符串 s 只包含小写拉丁字母，长度为 n。 保证所有测试用例的 n 之和不超过 5·10^5。 输出： 对于每个测试用例，输出美丽子串的数量。 示例： 输入： ``` 6 6 abaaba 1 a 2 aa 6 abcdef 12 accabccbacca 6 abbaaa ``` 输出： ``` 3 0 1 0 14 6 ``` 注意： 在第一个测试用例中，美丽子串有 "abaaba"、"baab"、"aa"。 在最后一个测试用例中，美丽子串有 "aa"（计算两次）、"abba"、"bb"、"bbaa"、"abbaaa"。