TLE во время строительства суффиксов массива ⇐ C++

[Anonymous]

Я пытался решить эту проблему «минимальное вращение» от CSE и решил использовать для этого массив суффиксов. Мой метод был простым, не добавляя «$» и сравнивать классы каждого элемента в массиве P, который содержит индекс подразделений (длина которой увеличивается в силах 2) в порядке возрастания. И в конце p [0] содержит индекс с самым низким порядком, если строка начинается с этого индекса.
Например: < /p>
String aba < /p>
a, b, a ---> p [0,2,1] c [0,1,0] < /p>
(0,1), (1,0), (0,0) ---> P [2,0,1] C [1,2,0] < /p>
Не удается на трех тестовых категориях с tle.
Есть ли что -то, что я могу сделать лучше, потому что я вижу сложность для этого O (nlogn) < /p>
#include
#include
#include
#include
#include

using namespace std;

void radixsort(vector &vec, vector &p) {
vector cnt(vec.size(),0);
for(int i = 0; i < vec.size(); i++) {
cnt[vec.second]++;
}
for(int i = 1; i < cnt.size(); i++){
cnt += cnt[i-1];
}

vector temp_p(p.size(), 0);
for(int i = vec.size() - 1; i >= 0; i--) {
temp_p[--cnt[vec.second]] = i;
}

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

for(int i = 0; i < vec.size(); i++) {
cnt[vec.first]++;
}
for(int i = 1; i < cnt.size(); i++){
cnt += cnt[i-1];
}

for(int i = temp_p.size()-1; i >= 0 ; i--) {
p[--cnt[vec[temp_p].first]] = temp_p;
}

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// ifstream MyReadFile("./test_input.txt");
string st;
cin>>st;
int ll = st.size();

// MyReadFile >> st;
// cout

Подробнее здесь: https://stackoverflow.com/questions/794 ... ffix-array