#P5671. pku2758 Checking the Text 文本校对
pku2758 Checking the Text 文本校对
题目描述
为了给Wind买生日礼物,Jiajia不得不找了一份检查文本的工作。这份工作很无聊:给你一段文本 要求比对从文本中某两个位置开始能匹配的最大长度是多少。但比无聊更糟糕的是,Jiajia的经理 还可能往文本里面插入一些字符。 Jiajia想用一个程序来解决这些繁琐的工作。这个程序的速度要足够快,因为Wind的生日就快要到了 Jiajia必须赚到足够多的钱,也就是处理足够多的文本。
输入格式
第一行输入原始文本,第二行输入操作数 。接下来 行,每行一条操作。
I ch p:在当前文本的第 个字符之前插入字符ch。如果 大于当前文本的长度,就在末尾追加。Q i j:找到原始文本的第 和第 个字符在当前文本中的位置。以这两个位置为起点,求当前文本中两个后缀的最长公共前缀长度。
位置从 开始编号。原始文本长度不超过 。插入操作至多 次,查询操作至多 次。
输出格式
每次查询输出一行一个整数,表示最长公共前缀长度。
样例
abaab
5
Q 1 2
Q 1 3
I a 2
Q 1 2
Q 1 3
0
1
0
3