[BZOJ1014/Luogu4036][JSOI2008]火星人prefix(字符串Hash,Splay,二分)

发布于 2018-04-01  157 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1014/Luogu4036][JSOI2008]火星人prefix(字符串Hash,Splay,二分)

Description

火星人最近研究了一种操作:求一个字串两个后缀的公共前缀。比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在,火星人定义了一个函数LCQ(x, y),表示:该字符串中第x个字符开始的字串,与该字符串中第y个字符开始的字串,两个字串的公共前缀的长度。比方说,LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程中,火星人发现了这样的一个关联:如果把该字符串的所有后缀排好序,就可以很快地求出LCQ函数的值;同样,如果求出了LCQ函数的值,也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速算法,但不甘心认输的地球人又给火星人出了个难题:在求取LCQ函数的同时,还可以改变字符串本身。具体地说,可以更改字符串中某一个字符的值,也可以在字符串中的某一个位置插入一个字符。地球人想考验一下,在如此复杂的问题中,火星人是否还能够做到很快地求取LCQ函数的值。

Tag

字符串Hash,Splay,二分

解决思路

想要求两个字符串的lcp,一种方法是把字符串后缀排序后,借助Height数组来求解。但是这样的缺点是不能支持修改操作。另一种就是二分长度+Hash判断。由于这里有对字符的修改和插入,所以采用二分+Hash的方式。
具体来说,相当于用Splay维护一个无序区间,对每一个点维护一个它子树内这段字符串的Hash值,每一次更改Splay形状的时候,顺便维护。那么,插入就把位置旋转到根再在后面插入,查询则把左端点的前一个转到根,右端点的后一个转到根的儿子,这样根的右儿子的左儿子就保存了需要的字符串Hash值。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1014/Luogu4036][JSOI2008]火星人prefix(字符串Hash,Splay,二分)


HNCJ OIer