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;

}