我现在要抨击一下boshi大神的做法,真是不够优美……
一份优美的代码应该是短,便于看懂而且能够AC的,所以说…..干嘛啊。
寻找循环节,其实跑一遍kmp就够了,如果存在循环节的话,肯定是n-next[n]这个长度的前缀。
比如说ababab,next[6]=4嘛,所以是长度为2的前缀。但是有的时候,这个前缀不可以完全覆盖整个字符串,比如说ababa这个情况,那么答案就是1。
所以我们就可以得到一份精炼而优美的代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
char s[1000005];
int ne[1000005];
int main()
{
    int i,j,kl,kkl;
    while(1){
        scanf("%s",s);ans=1;
        if(strcmp(s,".")==0)break;
        ne[1]=0;n=strlen(s);
        for(i=1;i<n;i++){
            j=ne[i];
            while(1){
                if(s[i]==s[j]){ne[i+1]=j+1;break;}
                if(!j){ne[i+1]=0;break;}
                j=ne[j];
            }
        }
        kl=n-ne[n];
        if(n%kl==0)ans=n/kl;//如果不能整除则最后几位不在循环节内
        printf("%d\n",ans);
    }
    return 0;
} 
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

4 条评论

蒟蒻XZY · 2017年4月24日 10:43 下午

亲爱的boshi,您好!
您还有1次怼dalao的机会,您的f降为1,等级降为0!

    boshi · 2017年4月25日 6:43 下午

    我现在再怼一次你然后我就不怼了

      蒟蒻XZY · 2017年4月26日 11:22 下午

      蛤?我如此弱怎成dalao了……
      唉,这还有49天我怎么熬过来啊!真想回J房……

boshi · 2017年4月24日 8:22 下午

你大爷
我那个简单易懂,条例清晰,不把东西都塞到main里

发表评论

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

你是机器人吗? =。= *