UVa455 最小周期串问题

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
2

#include <iostream>
#include<cstring>
#include <iomanip>
#include<string>
using namespace std;
int main(http://www.my516.com)
{
char a[81];
int n;
cin >> n;
while (n--)
{
cin >> a;
int t = 1;
while (true)
{
int c = 0;
for (int i = 0; i < strlen(a); i++)
{
if (a[i] == a[(i + t) % strlen(a)]) c++;
}
if (c == strlen(a)) break;
++t;
}
cout << t << endl;
if (n == 0) cout << endl;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
学习笔记：环形串问题可看成一个圆，只要圆转动几次后可回到原位，即最小周期，所以只需要看s[i]==s[(i+t)%len]。
---------------------

巴特西

UVa455 最小周期串问题

最新文章

热门文章