CF1827C.Palindrome Partition

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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$ .

输入格式

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$ .

输出格式

For each test case print the number of beautiful substrings.

输入输出样例

输入#1

6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa

输出#1

说明/提示

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".

首页