分数: 800 点
问题陈述
给你一个字符串 S 由字符组成 A 和 B.
在此字符串上,您可以重复执行以下操作:
- 选择三个连续的字符 S 等于
AABorBAA,然后删除这三个字符 S (删除后,剩余字符连接)。
查找可以执行此操作的最大次数。
T 给出了测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 10^5
- S 是一个由以下组成的字符串
A和B. - 1\leq |S|\leq 10^6
- 总和 |S| 单个输入中的所有测试用例最多 10^6.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
S
输出
打印 T 行。的 i- 第行应包含可以执行的最大操作数 i- 第一个测试用例。
示例输入 1
10 AABAAAB BAAAAABBA A B ABA BAA AAAAAA AAAABB AABABBAABBABAAAABBAA BBAAAAABAAAAABABAABA
示例输出 1
2 3 0 0 0 1 0 2 5 6
对于第一个和第二个测试用例,以下是执行最大操作数的可能方法:
AABAAAB→AAAB→ABAAAAABBA→BAAABA→BAA→(空字符串)