`
Coco_young
  • 浏览: 119162 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

[KMP-求循环节]HDU 3746 Cyclic Nacklace

 
阅读更多

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3746

题目大意:给定一个字符串,求出最少在末尾添加几个字符使得字符串成为循环串。

解题思路:先求出最小循环节,如果最小循环节长度等于字符串长度,则添加的字符数为字符串的长度,否则用字符串的长度模循环节的长度,如果为0,说明已经是循环串,如果非0,说明还要添加字符串长度减去该值个字符.

代码:

#include<iostream>
using namespace std;
const int MAXN = 111111;
int T,next[MAXN];
char s[MAXN],t[MAXN];
void makenext(char *s){
    int N = strlen(s);
    int i = 0,j = -1;
    next[0] = -1;
    while(i<=N){
        if(s[i]==s[j]||j==-1)next[++i]=++j;
        else j = next[j];
    }
}

int solve(){
    int N = strlen(s);
    int L = N-next[N];
    if(N==L)return N;
    if(N%L)return L-N%L;
    else return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        makenext(s);
        printf("%d\n",solve());
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics