| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴代码//KMP next 自匹配
#include <iostream>
using namespace std;
#define n 1000010
int Inext[n];
char Istr[n];
void getnext(char str[n],int next[n])
{
int i=0;
int l=strlen(str);
int j=-1;
next[0]=-1;
while(i<l)
{
if(j==-1 || str[j]==str[i])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
while(1)
{
scanf("%s",Istr);
if(!strcmp(Istr,".")) break;
getnext(Istr,Inext);
int len=strlen(Istr);
if(len%(len-Inext[len])==0)
printf("%d\n",len/(len-Inext[len]));
else
printf("%d\n",1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator