#3150. 回文子串 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

这是一道模板题。

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

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

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

输入格式

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

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

接下来 行,每行首先包含一个整数 ,其含义如下所示:

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

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

输出格式

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

样例

样例输入1

aaa
1
3

样例输出1

6

样例输入2

a
5
3
1 bba
3
2 ab
3

样例输出2

1
6
10

数据范围与提示

对于 的测试数据,保证有:

初始时 且操作序列结束时有