Nach einigem Lesen habe ich herausgefunden, was ein Suffix-Array und ein LCP-Array darstellen.

Suffix-Array: Stellt den _lexicographic-Rang jedes Suffix eines Arrays dar.

LCP-Array : Enthält die Übereinstimmung des Präfixes mit der maximalen Länge zwischen zwei aufeinanderfolgenden Suffixen, nachdem diese gefunden wurdenlexikographisch sortiert.

Ich habe seit ein paar Tagen versucht zu verstehen, wie genau das istSuffix-Array und LCP-Algorithmus funktioniert.

Hier ist der Code, aus dem entnommen wirdCodeforces:

/*
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

Ich kann einfach nicht durchkommen, wie dieser Algorithmus funktioniert. Ich habe versucht, mit Bleistift und Papier an einem Beispiel zu arbeiten, und habe die Schritte durchgearbeitet, aber die Verbindung dazwischen verloren, da sie zumindest für mich zu kompliziert ist.

Jede Hilfe in Bezug auf Erklärungen, vielleicht anhand eines Beispiels, wird sehr geschätzt.