HDU - 3374 - String Problem(最大与最小表示法+kmp求循环节)

HDU - 3374 - String Problem

个人博客

题意：

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

题解：

利用最小表示法与最大表示法O(n)复杂度求出最小字典序和最大字典序串出现位置，然后利用kmp求出next，利用next数组性质求出循环节次数，因为最小和最大字典序串出现次数等于循环节次数（这个关系可以脑补下）

代码：

#include<stdio.h>
#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 GetNex(){
    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)!=EOF){
        len=strlen(s);
        int sum=0;
        int mi=GetMin();//获取最小表示下标
        int mx=GetMax();//获取最大表示下标
        GetNex();
        if(len%(len-nex[len-1]-1)==0)sum=len/(len-nex[len-1]-1);
        else sum=1;
        printf("%d %d %d %d\n",mi+1,sum,mx+1,sum);
    }
    return 0;
}