#P17926. I Love CCPC

I Love CCPC

I Love CCPC

题目描述

一个仅含小写英文字母的字符串 t=t1t2⋯tkt=t_1t_2\cdots t_k 是 CCPC 串,当且仅当:

  • k≥4k\ge4;
  • t1=t2=tkt_1=t_2=t_k;
  • 中间的非空字符串 t3t4⋯tk−1t_3t_4\cdots t_{k-1} 是回文串。

例如 ccpc、ppap、zzzz、aabcddcba 是 CCPC 串,而 jinan、aaa、oovoo 不是。

给定字符串 ss,先统计其 CCPC 子串数量。随后执行 nn 次操作,每次在 ss 的左端或右端插入一个小写英文字母,输出每次操作后 CCPC 子串的数量。

子串由其左右端点确定。即使内容相同,只要端点不同,也算作不同的子串。

输入格式

第一行一个整数 TT,表示测试数据组数。每组数据:

第一行一个字符串 ss。

第二行一个整数 nn。

第三行 nn 个长度为 22 的字符串,表示操作。第一个字符是 L 或 R,分别表示左端、右端插入;第二个字符为要插入的小写英文字母。

输出格式

每组数据输出一行 n+1n+1 个整数:先输出初始答案,再依次输出每次操作后的答案。

数据范围

  • 1≤T≤1001\le T\le100,4≤∣s∣≤5×1054\le|s|\le5\times10^5,1≤n≤5×1051\le n\le5\times10^5。
  • ss 和插入字符均只含小写英文字母。
  • 所有测试数据的初始字符串长度之和不超过 5×1055\times10^5。
  • 所有测试数据的操作数之和不超过 5×1055\times10^5。

样例

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