旋转后按字典顺序排列的最小字符串

Question

我试图在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

您可以使用修改后的后缀数组。我的意思是修改，因为你不能停在单词末尾。

\n\n

这是类似问题的代码（SA是后缀数组）：

\n\n

//719\n//Glass Beads\n//Misc;String Matching;Suffix Array;Circular\n#include <iostream>\n#include <iomanip>\n#include <cstring>\n#include <string>\n#include <cmath>\n#define MAX 10050\nusing namespace std;\n\nint RA[MAX], tempRA[MAX];\nint SA[MAX], tempSA[MAX];\nint C[MAX];                \n\nvoid suffix_sort(int n, int k) {\n    memset(C, 0, sizeof C);        \n\n    for (int i = 0; i < n; i++)        \n        C[RA[(i + k)%n]]++;\n\n    int sum = 0;\n    for (int i = 0; i < max(256, n); i++) {                     \n        int t = C[i]; \n        C[i] = sum; \n        sum += t;\n    }\n\n    for (int i = 0; i < n; i++)        \n        tempSA[C[RA[(SA[i] + k)%n]]++] = SA[i];\n\n    memcpy(SA, tempSA, n*sizeof(int));\n}\n\nvoid suffix_array(string &s) {             \n    int n = s.size();\n\n    for (int i = 0; i < n; i++) \n        RA[i] = s[i];              \n\n    for (int i = 0; i < n; i++) \n        SA[i] = i;\n\n    for (int k = 1; k < n; k *= 2) {     \n        suffix_sort(n, k);\n        suffix_sort(n, 0);\n\n        int r = tempRA[SA[0]] = 0;\n        for (int i = 1; i < n; i++) {\n            int s1 = SA[i], s2 = SA[i-1];\n            bool equal = true;\n            equal &= RA[s1] == RA[s2];\n            equal &= RA[(s1+k)%n] == RA[(s2+k)%n];\n\n            tempRA[SA[i]] = equal ? r : ++r;     \n        }\n\n        memcpy(RA, tempRA, n*sizeof(int));\n    } \n}\n\nint main() {\n    int tt; cin >> tt;\n    while(tt--) {\n        string s; cin >> s;\n        suffix_array(s);\n        cout << SA[0]+1 << endl;\n   }\n}\n

\n\n

我主要从这本书中获取这个实现。有一个更容易编写的 O(n log\xc2\xb2n) 版本，但对于您的情况可能不够高效（n=10^5）。这个版本的时间复杂度为 O(n log n)，并且它不是最有效的算法。维基百科文章列出了一些 O(n) 算法，但我发现其中大多数都太复杂，无法在编程竞赛中编写。这个 O(n log n) 通常足以解决大多数问题。

\n\n

您可以在这里找到一些解释后缀数组概念的幻灯片（来自我提到的书的作者）。

\n