c++ - 旋转后字典序最小的字符串

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) 通常就足够了。

您可以找到一些解释后缀数组概念的幻灯片(来 self 提到的那本书的作者)here .