1. 题目

题目链接：UVA455「Periodic Strings」 。

Description

A character string is said to have period kk if it can be formed by concatenating one or more repetitions of another string of length kk. For example, the string abcabcabcabc has period 33, since it is formed by 44 repetitions of the string abc. It also has periods 66 (two repetitions of abcabc) and 1212 (one repetition of abcabcabcabc).

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

Input

The first line of the input file will contain a single integer NN 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 8080 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
2
1
HoHoHo

Sample Output

1
2

2. 题解

分析

字符串前缀函数的应用水题，结束。

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

// 前缀函数
struct PrefixFunction {
    #ifndef _PREFIXFUNCTION_
    #define ll int
    #define MAXN 10005
    #endif
    ll pi[MAXN];
    PrefixFunction() {}
    // 计算前缀函数数组
    void getPi(char *str, ll n) {
        pi[0] = 0;
        ll i = 1, j = pi[i-1];
        while(i < n) {
            if(str[i] == str[j]) {
                pi[i++] = j++ + 1;
            } else if(!j) {
                pi[i++] = j;
            } else {
                j = pi[j-1];
            }
        }
    }
};

int main()
{
    ll n;
    char str[MAXN];
    PrefixFunction pf;
    scanf("%d", &n);
    for(ll i = 0; i < n; ++i) {
        scanf("%s", str);
        ll len = strlen(str);
        pf.getPi(str, len);
        if(i) {
            printf("\n");
        }
        ll k = len - pf.pi[len-1];
        printf("%d\n", len%k ? len : k);
    }
    return 0;
}