首页 > 其他 > 详细

POJ 2406 Power Strings

时间:2014-03-31 22:38:24      阅读:548      评论:0      收藏:0      [点我收藏+]

KMP第二题   这次知道了前缀数组的另一奇葩所在。


题目大意:

给出一个字符串,某个子串链接n次产生的,求最大的n。


这一看KMP算法正合适啊,就啪啪写上了,但是WA。之后发现了这样子一组数据:aabaabaa

得特判啊~~


见代码:

#include <stdio.h>
#include <string.h>
char s[1000005];
int num[1000005];
int main()
{
    int n,case1=1;
    while(scanf("%s",s),s[0]!=‘.‘)
    {
        int j=-1;
        num[0]=-1;
        n=strlen(s);
        for(int i=0;i<n;)
        {
            if(j==-1||s[i]==s[j])num[++i]=++j;
            else j=num[j];
        }
        if(n%(n-num[n])==0)
        printf("%d\n",n/(n-num[n]));
        else puts("1");
    }
    return 0;
}


POJ 2406 Power Strings,布布扣,bubuko.com

POJ 2406 Power Strings

原文:http://blog.csdn.net/lin375691011/article/details/22691941

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!