String Problem HDU

题目链接

题意：给你一个字符串，问这个字符串经过移动后的字典序最小的字符串的首字符位置和字典序最大的字符串的首字符的位置，和能出现多少次最小字典序的字符串和最大字典序的字符串。

思路：用最小表示法和最大表示法O(n)求出下标，再根据next值的性质求解循环次数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+20;
const int mod=1e9+7;
char s[maxn];
int len;
int nex[maxn];
void GetNext(){
    memset(nex,0,sizeof(nex));
    int j=-1;
    for(int i=0;s[i];i++){
        while(s[i]!=s[j+1]&&j!=-1)j=nex[j];
        if(s[i]==s[j+1]&&i!=0)j++;
        nex[i]=j;
    }
}
int GetMin(){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(t>0)i=i+k+1;
            else j=j+k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return min(i,j);
}
int GetMax(){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(t>0)j=j+k+1;
            else i=i+k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return i<j?i:j;
}
int main()
{
    while(~scanf("%s",s))
    {
        len=strlen(s);
        int sum=0;
        int mi=GetMin();
        int mx=GetMax();
        GetNext();
        if(len%(len-nex[len-1]-1)==0)
            sum=len/(len-nex[len-1]-1);
        else 
            sum=1;
        printf("%d %d %d %d
",mi+1,sum,mx+1,sum);
    }
    return 0;
}