[HDOJ3374 String Problem]字符串循环的最小表示

【题目大意】

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

并分别输出这个串在循环中所出现的次数。

【算法分析】

利用经典算法求出他们最小表示的位置。然后用KMP算出现了几次。

【其它】

1A。

好像挺慢的。。。

【CODE】

#include #include

char s[2001111],p[1001111];
int next[1001111],n;

int minshow(){
    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 i}   

int maxshow(){
    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]) j+=k+1;
                          else i+=k+1;
            if (i==j) i++;
            k=0;
        }   
    }   
    return i}   

void kmp(int st){
    int i,j,ans=0;
    for (i=st,j=1;j<=n;i++,j++) p[j]=s[i];
   
    next[1]=0; j=0;
    for (i=2;i<=n;i++){
        while (j && p[j+1]!=p[i]) j=next[j];
        if (p[j+1]==p[i]) j++;
        next[i]=j;
    }   
   
    j=0;
    for (i=1;i<=n+n-1;i++){
        while (j && p[j+1]!=s[i]) j=next[j];
        if (p[j+1]==s[i]) j++;
        if (j==n){
            ans++;
            j=next[j];
        }   
    }   
    printf("%d %d",st,ans);
}   

int main(){
    while (scanf("%s",s+1)!=EOF){
        n=strlen(s+1);
        memcpy(s+n+1,s+1,sizeof(char)*n);
        kmp(minshow()); printf(" ");
        kmp(maxshow()); printf("n");
    }   
}