#include<cstdio>
#include<string>
using namespace std;
char num[61];
string n,r;
int f[61];
void ff(string P)
{
	int lenp=P.length(),j;
	f[0]=-1;
	for(j=1;j<lenp;j++)
	{
		int i=f[j-1];
		if(P[j]!=P[i+1]&&i>=0)
			i=f[i];
		if(P[j]==P[i+1])
			f[j]=f[i]+1;
		else
			f[j]=-1;
	}
}
int KMP(string T,string P)
{
	int lenp=P.length(),lent=T.length(),posP=0,posT=0;	
	while(posP<lenp&&posT<lent)
		if(P[posP]==T[posT])
		{
			posP++;posT++;
		}
		else if(posP==0)
			posT++;
		else
			posP=f[posP-1]+1;
	if(posP==lenp)
		return posT-lenp;
	else
		return -1;	
}
bool multi(string a,int r,string &b)
{
	int i,lena=a.length(),d;
	b=a;
	for(i=lena-1;i>=0;i--)
		b[i]=0;
	for(i=lena-1;i>1;i--)
	{
		d=a[i]*r+b[i];
		if(d>99)
		{
			b[i-2]+=d/100;
			d%=100;
		}
		if(d>9)
		{
			b[i-1]+=d/10;
			d%=10;
		}
		b[i]=d;
	}
	d=a[1]*r+b[1];
	if(d>99)
		return false;
	if(d>9)
	{
		b[0]+=d/10;
		d%=10;		
	}
	b[1]=d;
	d=a[0]*r+b[0];
	if(b[0]>9)
		return false;
	else
	{
		b[0]=d;
		return true;
	}
}
bool cyclic(string a,string b)
{
	string c;
	c=b;
	c+=b;
	ff(a);
	if(KMP(c,a)>-1)
		return true;
	else
		return false;	
}
int main()
{
	int len,i;
	while(scanf("%s",num))
	{
		len=strlen(num);
		n=num;
		for(i=0;i<len;i++)
			n[i]=num[i]-48;	
		for(i=1;i<=len;i++)
		{
			if(!multi(n,i,r))
				break;
			if(!cyclic(n,r))
				break;
		}
		if(i>len)
			printf("%s is cyclic\n",num);
		else
			printf("%s is not cyclic\n",num);
	}
	return 0;
}

• 原来是自己写的KMP太烂了。。。匹配时直接用string::find就过了 (0) bigheadghost 2006-11-14 21:21:28