构造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吧，我写得跟那个一样。