最小循环节 KMP poj2406

/*
题意:给出一个字符串 问它最多由多少相同的字串组成 
如 abababab由4个ab组成
详见蓝书P70 
对于一个有循环节的字符串 s[i-fail[i]+1 ~ i]==s[1 ~ fail[i]]是相同的
通过这个可以求出其最长循环节 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int nex[N];
char a[N];
void get(char s[],int len)
{
    nex[1]=0;
    for(int i=2,j=0;i<=len;i++){
        while(j>0&&a[i]!=a[j+1]) j=nex[j];
        if(a[i]==a[j+1]) j++;
        nex[i]=j;
    }
}
int main()
{
    while(scanf("%s",a+1)==1){
        int len=strlen(a+1);
        if(a[1]=='.'&&len==1) break;
        get(a,len);
        if(len%(len-nex[len])==0)
         printf("%d\n",len/(len-nex[len]));
        else printf("1\n");
    }
}

 

上一篇:KMP poj3942


下一篇:linux计划任务