即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

UVa 455 Periodic Strings

编程语言 bbbbswbq 12℃ 0评论

Problem Description

如果一个字符串可以由某个长度为k的字符串重复多次得到,则称该串以k为周期。例如,abcabcabc以3为周期

Sample Input

1


HoHoHo

Sample Output

2

代码:

#include
#include
int next[100];
void get_next(char s[])//获取next数组
{
    int i, j, len = strlen(s);
    next[0] = 0;
    for(i = 1; i < len; i++)
    {
        j = next[i-1];
        while(j > 0 && s[j] != s[i])
        {
            j = next[j - 1];
        }
        if(s[i] == s[j])
        {
            next[i] = j + 1;
        }
        else
        {
            next[i] = 0;
        }
    }
}
int main()
{
    int len, t, i;
    char str[100];
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", str);
        get_next(str);
        len = strlen(str);
        for(i = 0; i < len; i++)//判断是否是循环节
        {
            if(str[i] != str[(i + (len - next[len - 1]))%len]) break;//不是就break
        }
        if(i == len) printf("%d\n", (len - next[len - 1]));//else printf("%d\n", len);//输出长度
        if(t) printf("\n");
    }
    return 0;
}

转载请注明:CodingBlog » UVa 455 Periodic Strings

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情