Codeforces Global Round 26 |
---|
Закончено |
Вам дана строка $$$s$$$, состоящая из строчных латинских букв. Подсчитайте количество непустых строк $$$t \neq$$$ «$$$\texttt{a}$$$», таких, что можно разбить$$$^{\dagger}$$$ $$$s$$$ на некоторые подстроки, удовлетворяющие следующим условиям:
$$$^{\dagger}$$$ Разбиение строки $$$s$$$ — это упорядоченная последовательность некоторых $$$k$$$ строк $$$t_1, t_2, \ldots, t_k$$$ (называемых подстроками), таких, что $$$t_1 + t_2 + \ldots + t_k = s$$$, где $$$+$$$ обозначает операцию конкатенации строк.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит строку $$$s$$$, состоящую из строчных латинских букв ($$$2 \leq |s| \leq 2 \cdot 10^5$$$).
Гарантируется, что сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество непустых строк $$$t \neq$$$ «$$$\texttt{a}$$$», удовлетворяющих всем ограничениям.
8aaaaababacabacbaaabaaabitsetababbaaaabbbyearnineteeneightyfour
4 4 1 16 1 2 3 1
В первом наборе входных данных $$$t$$$ может быть «$$$\texttt{aa}$$$», «$$$\texttt{aaa}$$$», «$$$\texttt{aaaa}$$$» или всей строкой.
Во втором наборе входных данных $$$t$$$ может быть «$$$\texttt{b}$$$», «$$$\texttt{bab}$$$», «$$$\texttt{ba}$$$» или всей строкой.
В третьем наборе входных данных единственной подходящей $$$t$$$ является вся строка.
Название |
---|