Я пытаюсь решить эта проблема в спой
Мне нужно найти число вращений данной струны, которое сделает ее лексикографически наименьшей среди всех вращений.
Например:
Оригинал: ama
Первый поворот: maa
Второе вращение: aam
Это лексикографически наименьшее вращение, поэтому ответ 2.
Вот мой код:
string s,tmp;
char ss[100002];
scanf("%s",ss);
s=ss;
tmp=s;
int i,len=s.size(),ans=0,t=0;
for(i=0;i<len;i++)
{
string x=s.substr(i,len-i)+s.substr(0,i);
if(x<tmp)
{
tmp=x;
t=ans;
}
ans++;
}
cout<<t<<endl;
Я получаю «Превышен лимит времени» для этого решения. Я не понимаю, какие оптимизации можно сделать. Как я могу увеличить скорость своего решения?
Вы можете использовать модифицированный массив суффиксов. Я имею в виду изменение, потому что вы не должны останавливаться на конце слова.
Вот код для аналогичная проблема Я решил (SA является суффиксным массивом):
//719
//Glass Beads
//Misc;String Matching;Suffix Array;Circular
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 10050
using namespace std;
int RA[MAX], tempRA[MAX];
int SA[MAX], tempSA[MAX];
int C[MAX];
void suffix_sort(int n, int k) {
memset(C, 0, sizeof C);
for (int i = 0; i < n; i++)
C[RA[(i + k)%n]]++;
int sum = 0;
for (int i = 0; i < max(256, n); i++) {
int t = C[i];
C[i] = sum;
sum += t;
}
for (int i = 0; i < n; i++)
tempSA[C[RA[(SA[i] + k)%n]]++] = SA[i];
memcpy(SA, tempSA, n*sizeof(int));
}
void suffix_array(string &s) {
int n = s.size();
for (int i = 0; i < n; i++)
RA[i] = s[i];
for (int i = 0; i < n; i++)
SA[i] = i;
for (int k = 1; k < n; k *= 2) {
suffix_sort(n, k);
suffix_sort(n, 0);
int r = tempRA[SA[0]] = 0;
for (int i = 1; i < n; i++) {
int s1 = SA[i], s2 = SA[i-1];
bool equal = true;
equal &= RA[s1] == RA[s2];
equal &= RA[(s1+k)%n] == RA[(s2+k)%n];
tempRA[SA[i]] = equal ? r : ++r;
}
memcpy(RA, tempRA, n*sizeof(int));
}
}
int main() {
int tt; cin >> tt;
while(tt--) {
string s; cin >> s;
suffix_array(s);
cout << SA[0]+1 << endl;
}
}
Я взял эту реализацию в основном из эта книга. Существует более простая для написания O (n log²n) версия, но она может быть недостаточно эффективной для вашего случая (n = 10 ^ 5). Эта версия O (n log n), и это не самый эффективный алгоритм. В статье в Википедии перечислены некоторые алгоритмы O (n), но я считаю, что большинство из них слишком сложны, чтобы писать во время соревнования по программированию. Этого O (n log n) обычно достаточно для большинства проблем.
Вы можете найти несколько слайдов, объясняющих концепцию массива суффиксов (от автора упомянутой мной книги) Вот.
Я знаю, что это происходит очень поздно, но я наткнулся на это из Google в поиске еще более быстрого варианта этого алгоритма. Оказывается, хорошая реализация найдена в github: https://gist.github.com/MaskRay/8803371
Используется факторизация Линдона. Это означает, что он постоянно разбивает строку на лексикографически убывающие слова линдона. Слово Линдона — это строки, являющиеся (одним из) минимальных поворотов самих себя. Делая это по кругу, вы получите lms строки как последнее найденное слово линдона.
int lyndon_word(const char *a, int n)
{
int i = 0, j = 1, k;
while (j < n) {
// Invariant: i < j and indices in [0,j) \ i cannot be the first optimum
for (k = 0; k < n && a[(i+k)%n] == a[(j+k)%n]; k++);
if (a[(i+k)%n] <= a[(j+k)%n]) {
// if k < n
// foreach p in [j,j+k], s_p > s_{p-(j-i)}
// => [j,j+k] are all suboptimal
// => indices in [0,j+k+1) \ i are suboptimal
// else
// None of [j,j+k] is the first optimum
j += k+1;
} else {
// foreach p in [i,i+k], s_p > s_{p+(j-i)}
// => [i,i+k] are all suboptimal
// => [0,j) and [0,i+k+1) are suboptimal
// if i+k+1 < j
// j < j+1 and indices in [0,j+1) \ j are suboptimal
// else
// i+k+1 < i+k+2 and indices in [0,i+k+2) \ (i+k+1) are suboptimal
i += k+1;
if (i < j)
i = j++;
else
j = i+1;
}
}
// j >= n => [0,n) \ i cannot be the first optimum
return i;
}