UVA455「Periodic Strings」

1. 题目

题目链接：UVA455「Periodic Strings」 。

Description

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 666 (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 of 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

2. 题解

分析

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

代码

#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;
}