火星人的研究

题目描述:

火星人是一种好奇心很大的生物。最近，火星人对字符串产生了浓厚的兴趣。他们研究了字符串的LCP：

对于字符串str[1..n]，LCP(i, j)为str[i..n]与str[j..n]这两个字符串的公共前缀长。

例如str="madamimadam"：

m	a	d	a	m	i	m	a	d	a	m
1	2	3	4	5	6	7	8	9	10	11

有LCP(1, 7) = LCP("madamimadam", "madam") = 5

LCP(4, 8) = LCP("amimadam", "adam") = 1

LCP(10,11) = LCP("am", "m") = 0

后来，火星人发现，如果进行了后缀排序，就能够很快地求LCP，同样，如果能很快地求出字符串的LCP，也可以高效地把所有后缀排序。不过事情总不是想象的那么简单，地球人JS总是喜欢测试火星人的智商：他会在火星人把字符串的后缀排序以后，修改原来的字符串，导致火星人的工作全盘浪费。

于是火星人请到了聪明的你，设计一个程序，对给出的字符串能够支持以下三种操作：

1、求LCP(i, j)

2、将第i个位置的字符修改

3、在第i个位置后插入一个字符

火星人很害怕被地球人耻笑，所以希望你的算法能有很高的执行效率。

输入格式:

输入文件第一行为一个字符串（仅包含小写字母）。

接下来的一行的整数Q代表操作的个数（1 ≤Q  ≤150000）。

接下来Q行表示了待执行的操作。

Q i j表示求LCP(i, j)的数值

R i char表示将第i位置的字符替换成小写字母char

I i char表示在第i个字符后插入小写字母char

输出格式:

对于每一个Q i j，输出一行为LCP(i, j)的数值。

样例输入:

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

样例输出:

5
1
0
2
1

提示:

对于20%的数据，最终字符串的长度不超过1000。

对于另外30%的数据中不含有插入操作。

对于100%的数据，最终字符串的长度不超过100000。

对于100%的数据，替换字符的次数不超过100000。

对于100%的数据，询问LCP的次数不超过10000。

时间限制: 2000ms
空间限制: 256MB

---