Суффикстик структуралар

Суффикстик массив: саптын бардык суффикстерин иреттөө жана анын эмне берери.

Суффикстик массив — саптын бардык суффикстеринин иреттелген тизмеси (албетте, алардын баштапкы позициялары гана сакталат). Ал маселелердин бүтүндөй классын ачат: каалаган үлгүнү O(m log n) убакытта издөө, ар түрдүү сапчалардын саны, эки саптын эң узун жалпы сапчасы. «Түз» иреттөө менен куруу — O(n² log n): суффикстерди салыштыруу узак. Классикалык амал — экинин даражалары боюнча иреттөө: суффикстерди адегенде биринчи 1, анан 2, 4, 8... символу боюнча иреттейбиз. Ар бир кадамда суффикс мурунку кадамдагы эквиваленттик класстардын ТҮГӨЙҮ менен сүрөттөлөт — түгөйдү салыштыруу O(1).

Өзүңүз байкап көрүңүз — кодду өзгөртсө болот

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::string s;
    std::cin >> s;
    s += "$"; // терминальный символ меньше всех букв
    int n = s.size();

std::vector<int> order(n), cls(n);
    for (int i = 0; i < n; i++) order[i] = i;
    std::sort(order.begin(), order.end(), [&](int a, int b) { return s[a] < s[b]; });
    cls[order[0]] = 0;
    for (int i = 1; i < n; i++) {
        cls[order[i]] = cls[order[i - 1]] + (s[order[i]] != s[order[i - 1]] ? 1 : 0);
    }

for (int len = 1; len < n; len *= 2) {
        std::vector<std::pair<std::pair<int, int>, int>> t(n);
        for (int i = 0; i < n; i++) {
            t[i] = {{cls[i], cls[(i + len) % n]}, i};
        }
        std::sort(t.begin(), t.end());

for (int i = 0; i < n; i++) order[i] = t[i].second;
        cls[order[0]] = 0;
        for (int i = 1; i < n; i++) {
            cls[order[i]] = cls[order[i - 1]] + (t[i].first != t[i - 1].first ? 1 : 0);
        }
    }

std::cout << "Суффиксы по алфавиту:\n";
    for (int i = 1; i < n; i++) { // пропускаем суффикс из одного $
        std::cout << s.substr(order[i], n - 1 - order[i]) << "\n";
    }
    return 0;
}

Киргизүү маалыматтары (мисал — өзгөртсө болот)

O(n log² n) убакыттагы суффикстик массив. Киргизиңиз: banana

banana үчүн суффикстердин тартиби: a, ana, anana, banana, na, nana. Амалдардын талдоосу: • терминалдык $ символу (бардык тамгалардан кичине) суффикстерди «циклдик жылыштарга» теңейт — ошондуктан (i + len) % n иштейт; • эквиваленттик класс — «узундугу len болгон бирдей префикстердин тобунун номери»; (баштын классы, ортонун классы) түгөйү узундугу 2·len болгон префиксти толук сүрөттөйт; • std::sort ордуна саноо иреттөөсү менен классикалык O(n log n) чыгат. Теманын кийинки кадамы — LCP массиви (кошуна суффикстердин жалпы префикстеринин узундуктары, O(n) убакыттагы Касаи алгоритми): аны менен, мисалы, ар түрдүү сапчалардын саны эсептелет. Андан да күчтүүсү — суффикстик автомат, бирок ал массивди ишенимдүү өздөштүргөндөн кийин күтөт.

Тапшырма: banana суффикстик массивинин жардамы менен ар түрдүү сапчалардын санын кол менен эсептеңиз (суффикстердин узундуктарынын суммасы минус LCP суммасы; жооп: 15). Сабакты өттүм деп белгилеңиз.