CF1827C Palindrome Partition

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

N/A

N/A

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