#P5671. pku2758 Checking the Text 文本校对

    ID: 4672 传统题 1000ms 256MiB 尝试: 13 已通过: 3 难度: 7 上传者: 标签>难度分类提高字符串后缀数组排序与序列处理倍增计数排序Kasai 算法LCP+RMQ数据结构ST 表同向双指针CF2200

pku2758 Checking the Text 文本校对

题目描述

为了给Wind买生日礼物,Jiajia不得不找了一份检查文本的工作。这份工作很无聊:给你一段文本 要求比对从文本中某两个位置开始能匹配的最大长度是多少。但比无聊更糟糕的是,Jiajia的经理 还可能往文本里面插入一些字符。 Jiajia想用一个程序来解决这些繁琐的工作。这个程序的速度要足够快,因为Wind的生日就快要到了 Jiajia必须赚到足够多的钱,也就是处理足够多的文本。

输入格式

第一行输入原始文本,第二行输入操作数 nn。接下来 nn 行,每行一条操作。

  • I ch p:在当前文本的第 pp 个字符之前插入字符 ch。如果 pp 大于当前文本的长度,就在末尾追加。
  • Q i j:找到原始文本的第 ii 和第 jj 个字符在当前文本中的位置。以这两个位置为起点,求当前文本中两个后缀的最长公共前缀长度。

位置从 11 开始编号。原始文本长度不超过 5000050000。插入操作至多 200200 次,查询操作至多 2000020000 次。

输出格式

每次查询输出一行一个整数,表示最长公共前缀长度。

样例

abaab
5
Q 1 2
Q 1 3
I a 2
Q 1 2
Q 1 3
0
1
0
3