HDU 3374 exkmp+字符串最大最小表示法

题意

找到一个字符串中最先出现的最小(大)表示位置，和最小(大)表示串出现次数

分析

用最小(大)表示法求出最先出现的最小(大)表示位置，然后将串长扩两倍用exkmp找出现次数。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e6+10;
char s[maxn];
int n,nex[maxn];
int Get_min()
{
    int i = 0,j = 1,k = 0,t;
    while(i < n && j < n && k < n)
    {
        t = s[(i+k)%n] - s[(j+k)%n];
        if(!t) k++;
        else
        {
            if(t > 0) i += k+1;
            else j += k+1;
            if(i == j) j++;
            k = 0;
        }
    }
    return i >j ?j :i;
}
int Get_max()
{
    int i = 0,j = 1,k = 0,t;
    while(i < n && j < n && k < n)
    {
        t = s[(i+k)%n] - s[(j+k)%n];
        if(!t) k++;
        else
        {
            if(t > 0) j += k+1;
            else i += k+1;
            if(i == j) i++;
            k = 0;
        }
    }
    return i >j ?j :i;
}
int exkmp(int pos){
    int i=pos+1,j=0,p0=pos+1,cnt=1;
    while(i<2*n&&j<n&&s[i]==s[j+pos]) ++i,++j;
    nex[p0]=j;if(j==n) ++cnt;
    for(int i=pos+2;i<n;i++){
        j=max(0,min(nex[p0]+p0-i,nex[i-p0+pos]));
        if(i+j<nex[p0]+p0){
            nex[i]=j;
        }else{
            int k=i+j;
            while(k<2*n&&j<n&&s[k]==s[j+pos]) ++k,++j;
            nex[i]=j;p0=i;
        }
        if(nex[i]==n) ++cnt;
    }
    return cnt;
}
int main(){
    //ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    while(~scanf("%s",s)){
        n=strlen(s);
        for(int i=n;i<2*n;i++) s[i]=s[i-n];
        int j=Get_min();
        printf("%d %d ",j+1,exkmp(j));
        j=Get_max();
        printf("%d %d\n",j+1,exkmp(j));
    }
    return 0;
}