#P17926. I Love CCPC
I Love CCPC
I Love CCPC
题目描述
一个仅含小写英文字母的字符串 是 CCPC 串,当且仅当:
- ;
- ;
- 中间的非空字符串 是回文串。
例如 ccpc、ppap、zzzz、aabcddcba 是 CCPC 串,而 jinan、aaa、oovoo 不是。
给定字符串 ,先统计其 CCPC 子串数量。随后执行 次操作,每次在 的左端或右端插入一个小写英文字母,输出每次操作后 CCPC 子串的数量。
子串由其左右端点确定。即使内容相同,只要端点不同,也算作不同的子串。
输入格式
第一行一个整数 ,表示测试数据组数。每组数据:
第一行一个字符串 。
第二行一个整数 。
第三行 个长度为 的字符串,表示操作。第一个字符是 L 或 R,分别表示左端、右端插入;第二个字符为要插入的小写英文字母。
输出格式
每组数据输出一行 个整数:先输出初始答案,再依次输出每次操作后的答案。
数据范围
- ,,。
- 和插入字符均只含小写英文字母。
- 所有测试数据的初始字符串长度之和不超过 。
- 所有测试数据的操作数之和不超过 。
样例
2
iloveccpc
6
Rj Ri Ln La Ln Ln
cpcpccp
9
Lc Lc Rp Rc Lc Lc Rp Rp Rc
1 1 1 1 1 1 2
0 2 3 3 4 5 7 8 8 9