310396: CF1827C. 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
题意翻译
称一个字符串是好的，当且仅当它是一个长度为偶数的回文串或由若干长度为偶数的回文串拼接而成。 给定一个长度为 $n$ 的字符串 $s$，求有多少 $s$ 的子串是好的。 $1\le n\le5\times10^5$，$s$ 仅包含小写字母。Output
C. 回文分割
一个**子串**是指一个给定字符串中连续且非空的字母片段，不进行任何重排。
一个**偶数长度的回文串**是指从前往后和从后往前读都相同的字符串，并且长度为偶数。例如，字符串 "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"。题目大意： C. 回文分割 一个**子串**是指一个给定字符串中连续且非空的字母片段，不进行任何重排。 一个**偶数长度的回文串**是指从前往后和从后往前读都相同的字符串，并且长度为偶数。例如，字符串 "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"。