UVa OJ 455 Periodic Strings

Periodic Strings

A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string "abcabcabcabc" has period 3, since it is formed by 4 repetitions of the string "abc". It also has periods 6 (two repetitions of "abcabc") and 12 (one repetition of "abcabcabcabc").

Write a program to read a character string and determine its smallest period.

Input

The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line.

Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.

Sample Input

1

HoHoHo

Sample Output

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

    int kases;

    char s[100];

    scanf("%d",&kases);

    while (kases--)

    {

        scanf("%s",s);

        int length = strlen(s);

        for (int i = 1; i <= length; i++)

        {

            if (length%i == 0)

            {

                bool ok = true;

                for (int j = i; j < length; j++)

                    if (s[j] != s[j%i])

                    {

                        ok = false;

                        break;

                    }

                if (ok)

                {

                    printf("%d\n",i);

                    break;

                }

            }

        }

        if (kases != 0)

            printf("\n");

    }

    return 0;

}

本题没有难度，但由于没有认真审题，忽略了相邻两个输出之间要有空白行，提交了几次，认真审题是关键啊。

巴特西

UVa OJ 455 Periodic Strings

Input

Output

Sample Input

Sample Output

最新文章

热门文章