Skip to content

Tag Archives: Suffix Array

构造Suffix Array的DC3算法

Suffix Array这个东西的确非常有用,很多关于字符串处理的题目构造一个SA就能迎刃而解。最近在SPOJ上看到了题目SUBST1,一眼看出来是用SA解的,兴冲冲的写了个nlogn的算法,连测试数据都没有出就交上去,结果没有悬念的TLE了(按说n=50000时nlogn算法应该可以不TLE的,比如说给50000个数排序肯定就不会TLE,可见SA的常数之大)……于是没办法,只好开始学SA的线性算法。 找到了这篇论文,似乎就是大家所说的三分法的“Skew Algorithm”的原始出处。作者在文章里说这种算法的基本原理是“Difference Cover”原则,并且在采样(Sample)的时候以3为模,所以这个算法叫DC3(Difference Cover modulo 3)。在本文里这个算法的名字就以原始论文为准了。 DC3算法的基本过程是这样的:首先构造出来一个superstring,这个串的每个字母都是原串的字母拼接上后面的两个字母,但这个串仅包含原串中下标模3不为0的位置。(递归地)求出这个串的SA,设为SA12。显然SA12中串的排列顺序与最终结果SA的排列顺序是相同的,只是SA12包含的串只有原串的2/3。 然后利用这个SA12和原串在线性时间内求出没有包含在SA12中的1/3的串的SA(也就是下标模3为0的那些串),设为SA0。求SA0的方法是:串的初始顺序是它们后面那个串在SA12中的顺序,然后再依据第一个字母进行一次RadixSort就可以了。也就是说SA0中的顺序可以仅用两个关键字来确定:第一关键字是第一个字母,第二关键字是后面的那个串在SA12中的位置。 现在得到了SA0和SA12,只需要把它们合并就可以得到最终的SA了,要想在线性时间内完成合并,需要在常数时间内完成比较。其实也不太难:当模为0的一个串与模为1的一个串比较时,需要比较它们的第一个字母与它们后面的那个串(都在SA12中),当模为0的一个串与模为2的一个串比较时,需要比较它们的前两个字母与它们去掉前两个字母以后的那个串(显然也都在SA12中)。 具体实现有点麻烦,我目前的代码基本上是完全抄的论文后面给的C++程序。不过运行速度真的很理想。因为程序里有一个很强的优化:当superstring中所有的字符都不相同时,可以直接用一遍RadixSort得到SA12,不用递归。经过这样的优化,递归地层数非常少,对于完全随机生成的长度为50000的英文字符串,求一次SA平均只需进行4次调用。所以实际时间效率非常高,常数不算大。 目前我对这个算法的理解还远不够深刻,所以讲的可能不易理解。有能力的话就看上面给出的原始论文吧,只看前三节就可以,后面讲了如何以牺牲一定时间为代价优化空间使用,我们是完全用不着的。 实例代码见上面的论文的附录A吧,我写得跟那个一样。

利用 Sparse Table 构造 Suffix Array

特别注明:这个算法是我昨晚神经抽筋想出来的,目前其正确性与时间复杂度没有经过任何验证。经过一定验证了已经,见最后。 设原字符串为S,长度为N。定义二维数组st[0..N-1][0..F](st代表Sparse Table),其中F为N在二进制下的位数(F=[logN]+1)。st中任一元素的取值为[1,N]中的整数,且满足st[i][f]与st[j][f]的大小关系(小于、相等、大于)与S的子串S[i..i+2^f-1]和S[j..j+2^f-1]的大小关系一致。上述“子串”中的元素可能越界,故在算法中认为任何下标大于等于N的字符均为一个比任意字符都要小的字符(如’/0’)。在已知st[k][f-1](0<=k<N)的所有值之后,子串S[i..i+2^f-1]与所有长度相同的子串的相对大小完全取决于st[i][f-1]⊕st[i+2^(f-1)][f-1](⊕为连接运算),若i+2^(f-1)>=N,可简单地认为上述连接运算的右值为0,所以所有长度为2^f的子串可以利用基数排序的方法在O(n)的时间内排序,这个O(n)的排序基于的事实是:给定元素的两部分的取值均为[0,n])。所以说可以利用O(n)时间求出st[k][f]。初始时st[k][0]的取值可以利用一遍计数排序求出,更简单地,可以令st[k][0]=S[k](当S的长度小于字母表的大小时,这有可能违反st中元素取值为[1,N]的定义,但由于把字母表的大小看作常数,这样处理不会影响复杂度分析)。在求出st[k][F](0<=k<N)的所有值之后,可以看出st[k][F]体现了S[k..N-1]在所有后缀中的(相对)位置,再经过一遍基数排序,就得出了后缀数组。O(nlogn)的时间复杂度是显而易见的。空间复杂度也为O(nlogn),可以利用滚动数组优化成O(n)。另外,利用上述st表可以用O(1)时间回答S中任意两个子串的大小关系。 update: 使用USACO DEC06 GOLD 的 Patterns 一题测试,可以AC,这个算法的正确性应该没问题,效率嘛……反正比那个用hash做的标程要快许多。一共写了85行,其中求Suffix Array的核心部分大约40行。 示例程序:patterns.cpp