瑶瑶想找回文串

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

刚学完后缀数组求回文串的瑶瑶(tsyao)想到了另一个问题:如果能够对字符串做一些修改,怎么在每次询问时知道以某个字符为中心的最长回文串长度呢?因为瑶瑶整天只知道LOL,当他知道自己省选成绩的时候就天天在LOL,导致现在的她实在是太弱了,根本解决不了这个问题,于是就来找你帮忙,么么哒~你就帮帮她吗

Input

第一行为一个长度不超过100000字符串s作为初始字符串。第二行一个正整数n,表示操作/询问的个数。接下来n行,每行有如下几种可能出现的操作/询问:

Insert a x  在a处字符的后面插入一个字符x

Delete a  把a处字符删除

Update a x 把a处字符改为x

Query a 查询以a为中心的最长回文串长度

Output

对于每个询问,输出得到的最长回文串长度

Sample Input

baaaaab
5
Query 4
Delete 2
Query 3
Delete 4
Query 3

Sample Output

7
3
5

Hint

对于100%的数据 1<=n<=50000,字符串仅包含小写字母,保证操作过程中字符串长度不超过150000  (hint:请各位大胆写)

单组输入,共10组数据。

Source

zslzx

Manager

Information
Solved Number25
Submit Number101
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel