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

Question

Я пытаюсь решить this problem in spoj

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

Например:

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

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

Answer 1

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

Вот код для similar problem я решенный (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; 
    } 
} 

Я взял эту реализацию в основном из this book. Существует более простая версия O (n log²n), но может быть недостаточно эффективной для вашего случая (n = 10^5). Эта версия O (n log n), и это не самый эффективный алгоритм. В статье в Википедии перечислены некоторые алгоритмы O (n), но я считаю, что большинство из них слишком сложно писать во время конкурса программирования. Этот O (n log n) обычно достаточно для большинства проблем.

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

Answer 2

Я знаю, что это происходит очень поздно, но я наткнулся на это из Google на мой поиск еще более быстрого варианта этого алгоритма. Оказывается, хорошая реализация находится в github: https://gist.github.com/MaskRay/8803371

В нем используется факторизация lyndon. Это означает, что он снова разделяет строку на лексикографически уменьшающиеся слова Линдона. Слово Линдона - это строки, которые являются (одним из) минимальными вращениями самих себя. Выполнение этого круговым способом дает lms строки как последнее найденное слово lyndon.

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; 
}