题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3374
题目大意:
给你一个字符串,问这个字符串经过移动后的字典序最小的字符串的首字符位置和字典序最大的字符串的首字符的位置,和能出现多少次最小字典序的字符串和最大字典序的字符串
最大/小表示法。得到位置。循环次数:字符串的循环节。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int Next[1000005];
char s[1000005];
int get_next(char s[], int Len){
int i=0, j=-1;
Next[0]=-1;
while(i<Len){
if(j==-1||s[i]==s[j]){
i++, j++, Next[i]=j;
}
else{
j=Next[j];
}
}
}
int express(char s[], int n, int f){
int i=0, j=1, k=0;
while(i<n&&j<n&&k<n){
int t=s[(i+k)%n]-s[(j+k)%n];
if(f){//最小表示
if(!t)
k++;
else if(t>0)
i=i+k+1, k=0;
else
j=j+k+1, k=0;
if(i==j)
j++;
}
else{//最大表示
if(!t)
k++;
else if(t<0)
i=i+k+1, k=0;
else
j=j+k+1, k=0;
if(j==i)
j++;
}
}
return min(i, j);
}
int main() {
while(~scanf("%s", s)){
int Len=strlen(s);
get_next(s, Len);
int L=Len-Next[Len];
int cut=((Len%(L))==0?(Len/L):1);
printf("%d %d %d %d\n", express(s, Len, 1)+1, cut,express(s, Len, 0)+1, cut);
}
return 0;
}