[POJ1509 Glass Beads]字符串循环的最小表示、例题

【题目大意】

寻找最小字典序循环串起始位置

【算法分析】

围观了周源的论文。还是不懂，于是又来围观了某牛的blog，知道怎样做，但是感觉不能保证正确？

【CODE】

#include #include #include #include using namespace std;
int n;
char s[33333];

int minishow(){
int i=1,j=2,k=0;
while (i<=n && j<=n && k<=n){
if (s[i+k]==s[j+k]) k++;
else{
if (s[i+k]>s[j+k]) i+=k+1;
else j+=k+1;
if (i==j) i++;
k=0;
}   
}  
return min(i,j);
}   

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=0;iscanf("%s",s+1);
n=strlen(s+1);
for (int j=n+1;j<=n*2;j++) s[j]=s[j-n];
cout << minishow() << endl;
}   
}