Codeforces Round 793 (Div. 2) |
---|
Закончено |
Вам дана строка $$$s$$$ длины $$$n$$$, которая является палиндромом.
Вы должны посчитать количество индексов $$$i$$$ $$$(1 \le i \le n)$$$ таких, что строка после удаления $$$s_i$$$ из $$$s$$$ остается палиндромом.
Например, рассмотрим $$$s$$$ = «aba»
Палиндром — это строка, которая слева направо читается так же, как справа налево. Например, «abba», «a», «fef» являются палиндромами, а «codeforces», «acd», «xy» — нет.
Входные данные состоят из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — длину строки $$$s$$$.
Вторая строка каждого набора входных данных содержит строку $$$s$$$, состоящую из строчных английских букв. Гарантируется, что $$$s$$$ является палиндромом.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество индексов $$$i$$$ $$$(1 \le i \le n)$$$ таких, что строка после удаления $$$s_i$$$ из $$$s$$$ остается палиндромом.
33aba8acaaaaca2dd
1 4 2
Первый набора входных данных описан в условии.
Во втором наборе входных данных индексы $$$i$$$, которые приводят к палиндрому после удаления $$$s_i$$$, это $$$3, 4, 5, 6$$$. Следовательно, ответ — $$$4$$$.
В третьем наборе входных данных удаление любого из индексов приводит к «d», что является палиндромом. Следовательно, ответ равен $$$2$$$.
Название |
---|