相关疑难解决方法(0)

经过相当多的阅读后,我发现了后缀数组和LCP数组所代表的含义.

后缀数组:表示数组每个后缀的_lexicographic等级.

LCP数组:在按字典顺序排序后,包含两个连续后缀之间的最大长度前缀匹配.

几天以来,我一直在努力理解,后缀数组和LCP算法究竟是如何工作的.

这是代码,取自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] …