pku2758 Checking the Text 文本校对
时间限制：12s 空间限制：256MB
题目描述
为了给Wind买生日礼物，Jiajia不得不找了一份检查文本的工作。这份工作很无聊：给你一段文本
要求比对从文本中某两个位置开始能匹配的最大长度是多少。但比无聊更糟糕的是，Jiajia的经理
还可能往文本里面插入一些字符。
Jiajia想用一个程序来解决这些繁琐的工作。这个程序的速度要足够快，因为Wind的生日就快要到了
Jiajia必须赚到足够多的钱，也就是处理足够多的文本。
输入格式
输入文件第一行是原始文本。
输入文件第二行是操作数n。此后n行，每行描述一条命令，命令有两种形式：
I ch p：表示将一个字符ch插入到当前文本的第p个字符之前，如果p大于当前文本长度则表示插入到当前文本末尾；
Q i j：表示询问当前文本从原始文本的第i个和第j个字符现在所在的位置开始能匹配的字符是多少。
你可以认为文本初始长度不超过50000，I命令最多200条，Q命令最多20000条。
输出格式
对于每条Q命令输出一行，为最长匹配长度。
样例输入
abaab 5 Q 1 2 Q 1 3 I a 2 Q 1 2 Q 1 3
样例输出
0 1 0 3
提示
没有写明提示
题目来源
没有写明来源