POJ-2406-Power Strings(循环节)

博主链接

题目链接

题意:

给我们一个字符串,我们要求出它最多由几个相同的连续子串连接而成。也就是求最小循环节

题解:

先注意到如果他是循环子串那么n-next[n]一定是最小循环节。于是可以先求出nxt然后暴力匹配一遍看看。但是事实上只要满足n%(n-next[n])==0就可以保证答案正确了。

代码:

#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
char s[maxn];
int Next[maxn];
void Get_Nex(){
    int j=-1;
    for(int i=0;s[i];i++){
        while(s[i]!=s[j+1]&&j!=-1)j=Next[j];
        if(s[i]==s[j+1]&i!=0)j++;
        Next[i]=j;
    }
}
int main(){
    while(scanf("%s",s)){
        if(s[0]=='.')break;
        Get_Nex();
        int ans=1;
        int len=strlen(s);
        int L=Next[len-1];
        if(len%(len-L-1)==0)ans=len/(len-L-1);
        printf("%d\n",ans);
    }
    return 0;
}

全部评论

相关推荐

马上要带我人生中的第一个实习生了,想问问大家都喜欢什么的mentor?好让我有个努力的目标
拒绝996的劳伦斯很勇敢:看得见目标且护犊子的 具体就是明确告诉组员要干什么,然后当别的组甩dirty work时能护的组自家新人
点赞 评论 收藏
分享
04-14 20:10
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务