Суффиксный массив
Перейти к навигации
Перейти к поиску
Построение
Построение за Nlog2N:
vector<int> makeSuffixArray(string s) {
s += '\0';
int n = s.size();
vector<int> p(n);
for (int i = 0; i < n; i++)
p[i] = i;
sort(p.begin(), p.end(), [&](int i, int j) { return s[i] < s[j]; });
vector<int> rank(n);
rank[p[0]] = 0;
for (int i = 1; i < n; i++)
rank[p[i]] = rank[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
vector<pair<int, int>> rankPair(n);
for (int len = 1; len < n; len *= 2) {
for (int i = 0; i < n; i++)
rankPair[i] = { rank[i], rank[(i + len) % n] };
sort(p.begin(), p.end(), [&](int i, int j) { return rankPair[i] < rankPair[j]; });
rank[p[0]] = 0;
for (int i = 1; i < n; i++)
rank[p[i]] = rank[p[i - 1]] + (rankPair[p[i]] != rankPair[p[i - 1]]);
}
return p;
}
Построение за NlogN:
Меняем вызов sort() внутри цикла на следующий фрагмент:
for (int i = 0; i < n; i++)
p[i] = (p[i] - len + n) % n;
countSort(p, rank);
Здесь countSort() — сортировка подсчётом:
void countSort(vector<int> &p, const vector<int> &rank) {
int n = p.size();
vector<int> rankCount(n);
for (int i = 0; i < n; i++)
rankCount[rank[i]]++;
vector<int> rankFrom(n);
for (int i = 1; i < n; i++)
rankFrom[i] = rankFrom[i - 1] + rankCount[i - 1];
vector<int> sortedP(n);
for (int elem : p)
sortedP[rankFrom[rank[elem]]++] = elem;
p.swap(sortedP);
}
Поиск подстрок
int lowerBound(const string &s, const vector<int> &p, const string &t) {
int l = 0, r = p.size();
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (s.compare(p[m], t.size(), t) >= 0)
r = m;
else
l = m;
}
return r;
}
int upperBound(const string &s, const vector<int> &p, const string &t) {
int l = 0, r = p.size();
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (s.compare(p[m], t.size(), t) > 0)
r = m;
else
l = m;
}
return r;
}
int count(const string &s, const vector<int> &p, const string &t) {
return upperBound(s, p, t) - lowerBound(s, p, t);
}
Построение массива LCP
vector<int> makeLCP(const string &s, const vector<int> &p) {
int n = p.size();
vector<int> positionInP(n);
for (int i = 0; i < n; i++)
positionInP[p[i]] = i;
vector<int> lcp(n);
for (int i = 0, len = 0; i < n - 1; i++, len = max(len - 1, 0)) {
int j = p[positionInP[i] - 1];
while (s[i + len] == s[j + len])
len++;
lcp[positionInP[i]] = len;
}
return lcp;
}