OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【JSOI2008】火星人的研究

【题目描述】

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

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

例如str="madamimadam":

有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。

【题解】

噗……还以为真的有Dynamic Suffix Array啥的XD

我们考虑用一个Splay来维护字符串,这样替换和插入操作就解决了。现在问题是如何快速求出LCP,快速比较字符串可以用Hash完成,而求LCP可以二分这个长度。

设置一个质数作为Hash值,然后把维护这样一个key值:s[i]*hash^k+s[i+1]*hash^(k-1)+……+s[i+k-1]*hash+s[i+k]

维护方法很简单,左子树key值乘上hash的右子树大小+1次方加该节点值乘上hash的右子树大小次方加右子树key值即可(maya说出来感觉好混乱啊……)。

【代码】

再获1A~写完就能过真爽~

http://paste.ubuntu.com/10781580/

评论

© OI技术宅 | Powered by LOFTER