Codeforces Round 873 (Div. 1) |
---|
Закончено |
Подстрокой называется непрерывный и непустой подотрезок букв из данной строки, без изменения порядка.
Чётным палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево, и имеет чётную длину. Например, строки «zz», «abba», «abccba» являются чётными палиндромами, а строки «codeforces», «reality», «aba», «c» не являются.
Красивой строкой называется чётный палиндром или строка, которую можно разбить на несколько меньших чётных палиндромов.
Дана строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв. Подсчитайте количество красивых подстрок в $$$s$$$.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Затем следует их описание.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5\cdot 10^5$$$).
Вторая строка каждого набора входных данных содержит строку $$$s$$$. Строка $$$s$$$ состоит только из строчных латинских букв и имеет длину $$$n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5\cdot 10^5$$$.
Для каждого набора входных данных выведите количество красивых подстрок.
66abaaba1a2aa6abcdef12accabccbacca6abbaaa
3 0 1 0 14 6
В первом наборе входных данных красивыми подстроками являются «abaaba», «baab», «aa».
В последнем наборе входных данных красивыми подстроками являются «aa» (подсчитано дважды), «abba», «bb», «bbaa», «abbaaa».
Название |
---|