hdoj3374

最小表示法+kmp

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int next[1000000+10];
char s[2000000+10];
char t1[1000000+10],t2[1000000+10];
int min(int a,int b)
{
	return a<b?a:b;
}
int max(int a,int b)
{
	return a>b?a:b;
}

int minstr(char s[])
{
	int len=strlen(s);
	int i=0,j=1;
	while(i<=len-1 && j<=len-1)
	{
		int k=0;
		while(k<=len-1 && s[(i+k)%len]==s[(j+k)%len])
			k++;
		if(k>=len)
			break;
		if(s[(i+k)%len]>s[(j+k)%len])
			i=max(i+k+1,j+1);
		else
			j=max(j+k+1,i+1);
	}
	return min(i,j);
}

int maxstr(char s[])
{
	int len=strlen(s);
	int i=0,j=1;
	while(i<=len-1 && j<=len-1)
	{
		int k=0;
		while(k<=len-1 && s[(i+k)%len]==s[(j+k)%len])
				k++;
		if(k>=len)
			break;
		if(s[(i+k)%len]<s[(j+k)%len])
			i=max(i+k+1,j+1);
		else
			j=max(j+k+1,i+1);
	}
	return min(i,j);
}

void get_next(char t[])
{
	int len=strlen(t);
	int i=0,j=-1;
	next[0]=-1;
	while(i<=len-1)
	{
		if(j==-1 || t[i]==t[j])
		{
			i++;
			j++;
			if(t[i]!=t[j])
				next[i]=j;
			else
				next[i]=next[j];
		}
		else
			j=next[j];
	}
	return;
}
int kmp(char s[],char t[])
{
	int i=0,j=0;
	int cnt=0;
	int lens=strlen(s);
	int lent=strlen(t);
	while(i<=lens-1 && j<=lent-1)
	{
		if(j==-1 || s[i]==t[j])
		{
			i++;
			j++;
		}
		else
			j=next[j];
		if(j>=lent)
		{
			cnt++;
			j=next[j];
		}
	}
	return cnt;
}

int main()
{
	int i;
	while(scanf("%s",s)!=EOF)
	{
		getchar();
		int pos1,time1,pos2,time2;
		int len=strlen(s);
		pos1=minstr(s);
		pos2=maxstr(s);
		for(i=0;i<=len-2;i++)
			s[len+i]=s[i];
		s[len*2-1]='\0';
		for(i=pos1;i<=pos1+len-1;i++)
			t1[i-pos1]=s[i];
		for(i=pos2;i<=pos2+len-1;i++)
			t2[i-pos2]=s[i];
		t1[len]='\0';
		t2[len]='\0';
		get_next(t1);
		time1=kmp(s,t1);
		get_next(t2);
		time2=kmp(s,t2);
		printf("%d %d %d %d\n",pos1+1,time1,pos2+1,time2);


	
	}
//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>