我现在要抨击一下 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 里

发表回复

Avatar placeholder

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