HDU 3374 String Problem

最大最小表示法与KMP求循环节

最大最小表示法

最大最小表示法与KMP求循环节的模板题，

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

using namespace std;

const int MAXN=2000005;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

char s[MAXN],s1[MAXN],s2[MAXN];

int nxt[MAXN];

int MINR(){

	int i=0,j=1;

	int len=strlen(s)/2;

	while(i<len&&j<len){

		int k=0;

		while(s[i+k]==s[j+k]&&k<len) k++;

		if(k==len) break;

		if(s[i+k]>s[j+k]) i=max(i+k+1,j+1);

		else j=max(j+k+1,i+1);

	}

	int ans=min(i,j);

	for(int i=0;i<len;i++) s1[i]=s[i+ans];

	s1[len]='\0';

	return ans+1;

}

int MAXR(){

	int len=strlen(s)/2;

	int i=0,j=1;

	while(i<len&&j<len){

		int k=0;

		while(s[i+k]==s[j+k]&&k<len) k++;

		if(k==len) break;

		if(s[i+k]<s[j+k]) i=max(i+k+1,j+1);

		else j=max(j+k+1,i+1);

	}

	int ans=min(i,j);

	for(int i=0;i<len;i++) s2[i]=s[i+ans];

	s2[len]='\0';

	return ans+1;

}

void getnxt(char a[]){

	nxt[0]=-1;

	int k=-1,j=0;

	int len=strlen(a);//cout<<endl;cout<<len<<"               1"<<endl;

	while(j<len) if(k==-1||a[k]==a[j]) nxt[++j]=++k;

				 else k=nxt[k];

}

int kmp(char a[]){

	getnxt(a);

	int len=strlen(a);

	int ans=len-nxt[len];

	if(len==ans) return 1;

	if((len%ans)==0) return len/ans;

	else return 1;

}

int main(){

	freopen("in.txt","r",stdin);

	while(~scanf("%s",s)){

		int len=strlen(s);

		for(int i=0;i<len;i++) s[len+i]=s[i];

		s[len*2]='\0';

		int r1=MINR(),r2=MAXR();

		printf("%d %d %d %d\n",r1,kmp(s1),r2,kmp(s2));

		//cout<<s1<<s2<<endl;

	}

	fclose(stdin);

	return 0;

}