我正在尝试解决 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;
我收到此解决方案的“超出时间限制”。我不明白可以进行哪些优化。如何提高解决方案的速度?
最佳答案
您可以使用修改后的 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 .
关于c++ - 旋转后字典序最小的字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15002881/