[AdditionalFile141.zip](file://AdditionalFile141.zip?type=additional_file)

#141. 回文子串

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB | 显示标签 通过: 179 | 提交: 473

题目描述

这是一道模板题。

给定一个字符串 $s$ 以及 $Q$ 个操作。您需要编写一个程序以支持下列几种操作：

1. 在字符串 $s$ 的末尾添加一个字符串；
2. 在字符串 $s$ 的前端添加一个字符串的反序；
3. 查询字符串 $s$ 的所有非空回文串的数量。

$s$ 的两个子串视为不同，当且仅当这两个子串的长度不同或者这两个子串在 $s$ 中的起始位置不同。$s$ 的反序字符串定义为将 $s$ 中前后对称位置的字符两两对调位置后形成的字符串。

输入格式

输入文件第一行包含一个字符串 $s$。

输入文件第二行包含一个整数 $Q$，表示操作的数量。

接下来 $Q$ 行，每行首先包含一个整数 $op$，其含义如下所示：

• 1：在字符串 $s$ 的末尾添加一个字符串；
• 2：在字符串 $s$ 的前端添加一个字符串的反序；
• 3：查询字符串 $s$ 的所有非空回文串的数量。

若 $op$ 为 1 或 2，则接下来会给出一个字符串 $t$，表示要在末尾或前端添加的字符串。

输出格式

对于每个 $op$ 为 3 的操作，分别在单独的一行上输出此时 $s$ 中非空回文串的数量。

样例 1

输入

aaa
1
3

输出

6

样例 2

输入

a
5
3
1 bba
3
2 ab
3

输出

1
6
10

数据范围与提示

对于 100% 的测试数据，保证有：

初始时 $0 < |s| \le 10^5$, $0 < Q \le 10^5$, $0 < |t| < 1000$ 且操作序列结束时时有 $0 < |s| \le 4 \times 10^5$。