1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
struct SuffixArray { // MAX_LG = ceil(log2(MAX_N))
static const int MAX_N = 100010, MAX_LG = 17;
pair<pair<int, int>, int> L[MAX_N];
int P[MAX_LG + 1][MAX_N], n, step, count;
int suffixArray[MAX_N], lcpArray[MAX_N];
SuffixArray(const string &s) : n(s.size()) { // Laufzeit: O(n*log^2(n))
for (int i = 0; i < n; i++) P[0][i] = s[i];
suffixArray[0] = 0; // Falls n == 1.
for (step = 1, count = 1; count < n; step++, count <<= 1) {
for (int i = 0; i < n; i++) L[i] =
{{P[step-1][i], i+count < n ? P[step-1][i+count] : -1}, i};
sort(L, L + n);
for (int i = 0; i < n; i++) P[step][L[i].second] = i > 0 &&
L[i].first == L[i-1].first ? P[step][L[i-1].second] : i;
}
for (int i = 0; i < n; i++) suffixArray[i] = L[i].second;
for (int i = 1; i < n; i++)
lcpArray[i] = lcp(suffixArray[i - 1], suffixArray[i]);
}
// x und y sind Indizes im String, nicht im Suffixarray.
int lcp(int x, int y) { // Laufzeit: O(log(n))
int k, ret = 0;
if (x == y) return n - x;
for (k = step - 1; k >= 0 && x < n && y < n; k--)
if (P[k][x] == P[k][y])
x += 1 << k, y += 1 << k, ret += 1 << k;
return ret;
}
};
|
