Суффиксный массив: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Построение == Построение за Nlog<sup>2</sup>N: vector<int> makeSuffixArray(string s) { s += '\0'; int n = s.size(); ve…»)
 
Нет описания правки
Строка 29: Строка 29:
   
   
     return p;
     return p;
}


Построение за NlogN:
Построение за NlogN:


Меняем вызов <tt>sort()</tt> на следующий фрагмент:
Меняем вызов <tt>sort()</tt> внутри цикла на следующий фрагмент:
  for (int i = 0; i < n; i++)
  for (int i = 0; i < n; i++)
     p[i] = (p[i] - len + n) % n;
     p[i] = (p[i] - len + n) % n;
Строка 53: Строка 54:
         sortedP[rankFrom[rank[elem]]++] = elem;
         sortedP[rankFrom[rank[elem]]++] = elem;
     p.swap(sortedP);
     p.swap(sortedP);
}


== Поиск подстрок ==
== Поиск подстрок ==

Версия от 17:51, 22 февраля 2020

Построение

Построение за 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 count(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;
    }
    int lb = r;

    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;
    }
    int ub = r;

    return ub - lb;
}

Ссылки