лексикографически самая маленькая строка после вращения

Question

лексикографически самая маленькая строка после вращения

Я пытаюсь решить эта проблема в спой

Мне нужно найти число вращений данной струны, которое сделает ее лексикографически наименьшей среди всех вращений.

Например:

Оригинал: 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;

Я получаю «Превышен лимит времени» для этого решения. Я не понимаю, какие оптимизации можно сделать. Как я могу увеличить скорость своего решения?

9

algorithm c++lexicographic string

Решение

Другие решения

Я знаю, что это происходит очень поздно, но я наткнулся на это из 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;
}

1

Источник

Accepted Answer

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

Вот код для аналогичная проблема Я решил (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) обычно достаточно для большинства проблем.

Вы можете найти несколько слайдов, объясняющих концепцию массива суффиксов (от автора упомянутой мной книги) Вот.

2