利用 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