Суффмасс

Суффиксный массив - массив отсорченых в лексикографическом порядке суффиксов строки

abracadabra

a

abra

abracadabra

acadabra

adabra

bra

bracadabra

cadabra

dabra

ra

racadabra

построение за Nlog^2N

Пишем свой компаратор для сорт, где с помощью бинпоиска + хешей ищем наибольший общий префикс, сравниваем следующий за ним символ

построение за NlogN

Будем сортировать циклические сдвиги строки, предварительно записав в ее конец специальный символ, меньший остальных.

Тогда будем сортить для длины суффикса 1, 2, 4, 8...

будем красить все в цвета так, что номера цветов идут по возрастанию и хранить такой цвет для каждого суффикса.

тогда мы мерджим два отрезка - нам только остается отсортить пары по цвету за N

сортим подсчетом по правой, а потом по левой. профит

vector<vector<int>> cnt(n);

vector<int> col(n);

vector<int> cur;

for(int i = 0; i < n; i++){

col[i] = s[i] - '#';

cnt[col[i]].push_back(i);

}

int l = 2;

for(int i = 0; i < cnt.size(); i++){

for(auto it : cnt[i]){

cur.push_back(it);

}

}

while(l < n){

vector<pair<int,int>> p(n);

cnt.resize(n);

for(int i = 0; i < n; i++){

p[cur[i]].first = col[cur[i]];

p[cur[i]].second = col[(cur[i] + l) % n];

cnt[p[cur[i]].second].push_back(cur[i]);

}

cur.clear();

for(int i = 0; i < cnt.size(); i++){

for(auto it : cnt[i]){

cur.push_back(it);

}

}

cnt.resize(n);

for(int i = 0; i < n; i++){

cnt[p[cur[i]].first].push_back(cur[i]);

}

cur.clear();

for(int i = 0; i < cnt.size(); i++){

for(auto it : cnt[i]){

cur.push_back(it);

}

}

col[cur[0]] = 0;

for(int i = 1; i < n; i++){

if(p[cur[i]].first == p[cur[i-1]].first&&p[cur[i]].second == p[cur[i-1]].second){

col[cur[i]] = col[cur[i-1]];

}

else{

col[cur[i]] = col[cur[i-1]] + 1;

}

}

l *= 2;

}

LCP

будем искать для каждых двух суффиксов в суффмассе наибольший общий префикс. Будем делать это явно - заметим, что если мы для суффикса i нашли ответ x, то для суффикса i+1 ответ минимум x-1. Тогда мы переприсваеваем явно и передвигаем указатель. Это работает за О(N).