后缀数组algorithm
在阅读了一段时间之后，我已经想出了一个后缀数组和LCP数组代表了什么。
后缀数组 ：表示数组中每个后缀的_lexicographic等级。
LCP数组 ：包含两个连续后缀之间的最大长度前缀匹配， 按照字典顺序sorting 。
我已经努力了解了几天， 后缀数组和LCPalgorithm的工作原理。
这是从Codeforces获取的代码：
/* Suffix array O(n lg^2 n) LCP table O(n) */ #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); ++i) namespace SuffixArray { const int MAXN = 1 << 21; char * S; int N, gap; int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN]; bool sufCmp(int i, int j) { if (pos[i] != pos[j]) return pos[i] < pos[j]; i += gap; j += gap; return (i < N && j < N) ? pos[i] < pos[j] : i > j; } void buildSA() { N = strlen(S); REP(i, N) sa[i] = i, pos[i] = S[i]; for (gap = 1;; gap *= 2) { sort(sa, sa + N, sufCmp); REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]); REP(i, N) pos[sa[i]] = tmp[i]; if (tmp[N - 1] == N - 1) break; } } void buildLCP() { for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1) { for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];) ++k; lcp[pos[i]] = k; if (k)--k; } } } // end namespace SuffixArray 我不能，只是不能通过这个algorithm如何工作。 我试着用铅笔和纸做一个例子，并且通过所涉及的步骤写下来，但是至less在我之间失去了联系，因为它太复杂了。
任何有关解释的帮助，使用一个例子，也许，高度赞赏。
概观
这是用于后缀数组构造的O（n log n）algorithm（或者说，如果不使用::sort ，则使用2-pass桶sorting）。
它首先对原始stringS的2克（*） ，然后是4克，然后是8克等等进行sorting，所以在第i次迭代中，我们对2个i- 。 显然可以不超过log 2 （n）这样的迭代，而诀窍在于通过确保两个2个i- gram的每个比较在O中完成，便于在第i个步骤中对2个i -grams进行sorting（1）时间（而不是O（ 2i ）时间）。
这是怎么做到的？ 那么， 在第一次迭代它sorting2克（又名bigrams），然后执行所谓的字典重命名 。 这意味着它会创build一个新的数组（长度为n ），用于存储两个bigram在bigramsorting中的排名 。
词典重命名的例子：假设我们有一些bigrams {'ab','ab','ca','cd','cd','ea'}的sorting列表。 然后，我们从左到右分配排名 （即词典名称），从0开始，每当遇到新的 bigram时增加排名。 所以我们分配的队伍如下：
ab : 0 ab : 0 [no change to previous] ca : 1 [increment because different from previous] cd : 2 [increment because different from previous] cd : 2 [no change to previous] ea : 3 [increment because different from previous]
这些等级被称为词典名称 。
现在， 在下一个迭代中 ，我们sorting4克。 这涉及到很多不同的4克之间的比较。 我们如何比较两个4克？ 那么，我们可以按字符比较它们。 每个比较最多可以有4次操作。 相反，我们通过使用前面步骤中生成的等级表来查找它们中包含的两个正整数的等级来比较它们。 这个排名代表了以前2克sorting的词典排名，所以如果对于任何给定的4克，其第一个2克排名高于另一个4克排在第一个2克的排名，那么它必须按字典顺序更大在前两个字符的某处 。 因此，如果对于两个4克，第一个2克的等级是相同的，它们在前两个字符中必须是相同的。 换句话说，排名表中的两个查找就足以比较两个4-gram的全部4个字符。
sorting后，我们再次创build新的词典名称，这次是4克。
在第三次迭代中，我们需要按8克sorting。 再一次，在上一步的词典等级表中查找两个足以比较两个给定8-gram的全部8个字符。
等等。 每次迭代i有两个步骤：
-
按照2个i -gram进行sorting，使用前一次迭代的词典名称，以两个步骤（即O（1）时间）进行比较
-
创build新的词典名称
我们重复这个，直到所有2个I -grams都不一样。 如果发生这种情况，我们就完成了。 我们怎么知道所有的都不一样？ 那么，词典名称是一个递增的整数序列，从0开始。因此，如果在迭代中生成的最高词典名称与n-1相同，那么每个2个I- gram都必须被赋予其自己的不同的词典名称。
履行
现在让我们看看代码来确认所有这些。 使用的variables如下： sa[]是我们正在build立的后缀数组。 pos[]是等级查找表（即它包含词典名称），具体而言， pos[k]包含上一步的第k个m-gram的词典名称。 tmp[]是一个辅助数组，用于帮助创buildpos[] 。
我将在代码行之间给出进一步的解释：
void buildSA() { N = strlen(S); /* This is a loop that initializes sa[] and pos[]. For sa[] we assume the order the suffixes have in the given string. For pos[] we set the lexicographic rank of each 1-gram using the characters themselves. That makes sense, right? */ REP(i, N) sa[i] = i, pos[i] = S[i]; /* Gap is the length of the m-gram in each step, divided by 2. We start with 2-grams, so gap is 1 initially. It then increases to 2, 4, 8 and so on. */ for (gap = 1;; gap *= 2) { /* We sort by (gap*2)-grams: */ sort(sa, sa + N, sufCmp); /* We compute the lexicographic rank of each m-gram that we have sorted above. Notice how the rank is computed by comparing each n-gram at position i with its neighbor at i+1. If they are identical, the comparison yields 0, so the rank does not increase. Otherwise the comparison yields 1, so the rank increases by 1. */ REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]); /* tmp contains the rank by position. Now we map this into pos, so that in the next step we can look it up per m-gram, rather than by position. */ REP(i, N) pos[sa[i]] = tmp[i]; /* If the largest lexicographic name generated is n-1, we are finished, because this means all m-grams must have been different. */ if (tmp[N - 1] == N - 1) break; } }
关于比较function
函数sufCmp用于按照字典顺序比较两个（2 *间隙）。 所以在第一次迭代中，它比较了bigrams，在第二次迭代中，4-grams，然后是8-g，等等。 这是由gap控制的，这是一个全局variables。
sufCmp一个天真的实现将是这样的：
bool sufCmp(int i, int j) { int pos_i = sa[i]; int pos_j = sa[j]; int end_i = pos_i + 2*gap; int end_j = pos_j + 2*gap; if (end_i > N) end_i = N; if (end_j > N) end_j = N; while (i < end_i && j < end_j) { if (S[pos_i] != S[pos_j]) return S[pos_i] < S[pos_j]; pos_i += 1; pos_j += 1; } return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j; }
这将比较在第i个后缀pos_i:=sa[i]的开始处的（2 * gap）-gram与在第j个后缀pos_j:=sa[j]的开始处find的那个。 并将它们按字符进行比较， S[pos_i]与S[pos_j] ，然后将S[pos_i+1]与S[pos_j+1]进行比较等等。 只要字符相同，它就会继续。 一旦它们不同，如果第i个后缀中的字符小于第j个后缀中的字符，则返回1，否则返回0。 （注意return a<b在一个函数返回int意味着你返回1，如果条件是真的，0，如果是假的。
返回语句中的复杂外观条件处理（2 *间隙）图中的一个位于string末尾的情况。 在这种情况下， pos_i或pos_j将在所有（2 *间隔）字符进行比较之前达到N ，即使到此为止的所有字符都相同。 如果第i个后缀在结尾，则返回1;如果第j个后缀在结尾，则返回0。 这是正确的，因为如果所有字符都是相同的，则较短的一个按字典顺序较小。 如果pos_i已经达到最后，则第i个后缀必须比第j个后缀短。
显然，这个天真的实现是O（间隙），即它的复杂度在（2 *间隙）图的长度上是线性的。 然而，在你的代码中使用的函数使用字典名称来将它放到O（1）（具体地说，最多可以有两个比较）：
bool sufCmp(int i, int j) { if (pos[i] != pos[j]) return pos[i] < pos[j]; i += gap; j += gap; return (i < N && j < N) ? pos[i] < pos[j] : i > j; }
正如你所看到的，我们不是查找单个字符S[i]和S[j] ，而是检查第i个和第j个后缀的字典顺序。 在先前的迭代中计算了词典排名。 所以，如果pos[i] < pos[j] ，那么第i个后缀sa[i]必须以比sa[j]开头的gap-gram小的字符间距开始。 换句话说，通过查找pos[i]和pos[j]并比较它们，我们比较了两个后缀的第一个空格字符。
如果等级相同，我们继续比较pos[i+gap]和pos[j+gap] 。 这与（2 *间隙） – 即下半部分的下一个间隔字符的比较是相同的。 如果等级再次相等，那么两个（2 *间隙）图就是相同的，所以我们返回0.否则，如果第i个后缀小于第j个后缀，则返回1，否则为0。
例
下面的例子说明了algorithm是如何操作的，并且特别演示了字典名称在sortingalgorithm中的作用。
我们要sorting的string是abcxabcd 。 为此需要三次迭代来生成后缀数组。 在每次迭代中，我将显示S （string）， sa （后缀数组的当前状态）以及tmp和pos ，它们代表字典名称。
首先，我们初始化：
S abcxabcd sa 01234567 pos abcxabcd
请注意，最初代表unigrams的字典级别的字典名称与字符（即unigrams）本身是如何相同的。
第一次迭代：
对sa进行sorting，使用bigrams作为sorting标准：
sa 04156273
前两个后缀是0和4，因为这些是bigram'ab'的位置。 然后1和5（bigram'bc'的位置），然后是6（bigram'cd'），然后是2（bigram'cx'）。 然后7（不完整的bigram'd'），然后3（bigram'xa'）。 显然，这些职位与订单相对应，完全基于字符两字。
生成词典名称：
tmp 00112345
如上所述，词典名称被分配为递增整数。 前两个后缀（都以bigram'ab'开始）得到0，接下来的两个（都以bigram'bc'开头）得到1，然后是2,3,4,5（每个都是不同的二元组）。
最后，我们根据sa的位置来映射它，得到pos ：
sa 04156273 tmp 00112345 pos 01350124
（ pos的生成方式是这样的：从左到右通过sa ，并使用该条目在pos定义索引，使用tmp相应的条目来定义该索引的值，所以pos[0]:=0 ， pos[4]:=0 ， pos[1]:=1 ， pos[5]:=1 ， pos[6]:=2等等，索引来自tmp的值。
第二次迭代：
我们再次分类sa ，再次从pos （每个代表原始string的两个 bigrams序列）中查看bigrams。
sa 04516273
请注意，与之前的sa版本相比，1 5的位置是如何切换的。 它曾经是15，现在是51，这是因为pos[1]的bigram和pos[5]的bigram曾经在前一次迭代中是相同的（都是bc ），而现在是pos[5]是12 ，而pos[1]的双精度是13 。 所以位置5 在位置1 之前 。 这是因为词典名称现在分别代表原始string的bigrams： pos[5]代表bc ， pos[6]代表'cd'。 所以他们一起代表bcd ，而pos[1]代表bc ， pos[2]代表cx ，所以他们一起代表bcx ，这实际上在词典上大于bcd 。
再次，我们通过从左到右筛选sa的当前版本并比较pos相应的bigrams来生成词典名称：
tmp 00123456
前两个条目仍然是相同的（均为0），因为pos中对应的两个条目都是01 。 剩下的就是一个严格递增的整数序列，因为pos中的所有其他bigrams都是唯一的。
我们像以前一样执行到新pos的映射（从sa和tmp值中获取索引）：
sa 04516273 tmp 00123456 pos 02460135
第三次迭代：
我们再次分类sa ，并且把pos （一如既往），现在每个代表一系列原始string的四个字符。
sa 40516273
你会注意到，现在前两个条目已经转换了位置： 04已经变成了40 。 这是因为pos[0]的bigram是02而pos[4]中的那个是01 ，后者显然是词典上较小的。 深层次的原因是这两个分别代表abcx和abcd 。
生成字典名称产生：
tmp 01234567
它们都是不同的，即最高的是7 ，这是n-1 。 所以，我们已经完成了，因为sorting现在是基于所有不同的m-gram。 即使我们继续，sorting顺序也不会改变。
改进build议
用于对每个迭代中的2个i -gram进行sorting的algorithm似乎是内置sort （或std::sort ）。 这意味着它是一个比较sorting，在最坏的情况下， 每次迭代都需要O（n log n）时间。 由于在最坏的情况下有log n迭代，所以这使得它成为O（n（log n） 2 ）时间algorithm。 但是，sorting可以通过使用两次桶sorting来完成，因为我们用于sorting比较的键（即上一步的词典名）会形成一个递增的整数序列。 所以这可以被改进为用于后缀sorting的实际的O（n log n）时间algorithm。
备注
我相信这是1992年由Manber和Myers撰写的关于后缀数组构build的原始algorithm（ 链接在Google Scholar上 ;它应该是第一个命中，并且可能有链接到PDF的链接）。 这（同时，但是独立于Gonnet和Baeza-Yates的论文）是引入了后缀数组（当时也称为pat数组）作为有待进一步研究的数据结构。
用于后缀数组结构的现代algorithm是O（n），所以上面不再是最好的algorithm（至less不是理论上的，最坏的情况）。
脚注
（*） 2-gram是指原始string的两个连续字符序列。 例如，当S=abcde是string时， ab ， bc ， cd ， de是S的2-gram。 同样， abcd和bcde是4克。 通常，m-gram（对于正整数m）是m个连续字符的序列。 1克也叫unigrams，2克被称为bigrams，3克被称为trigrams。 有些人继续四列，五angular星等。
请注意， S起始和位置i的后缀是S的（ni）-gram。 而且，每个m-gram（对于任何m）都是S的后缀之一的前缀。 因此，sortingm-gram（对于尽可能大的m）可以是sorting后缀的第一步。
正如你已经为此CodeGo.net visces，我相信你也熟悉Topcoder :)请检查下面的链接，它也有更多的链接。 我见过很多人只从这些链接学习后缀数组。
TopCoder链接在这里
而编程参赛者则是一块黄金。 我从这篇文章中学习了Suffix数组
