跳转至

POJ1961

知识点

  • 前缀函数

题意简述

给定一个长度为 \(n\) 的字符串 \(S\)\(\forall i \in [1, n]\),求 $$ k \in (1, n], \text{s.t. } \exists x \in \Sigma^{\star}, S_i = x^k $$ 多组数据1

数据范围:\(2 \le n \le 10^6\)

解题思路

引理

对任意字符串 \(S\),恒有 \(x^k = S \Longleftrightarrow [k | n] \land [S[1..n - k] = S[k + 1..n]]\)

证明
  • 先证明 \(x^k = S \Longrightarrow [k | n] \land [S[1..n - k] = S[k + 1..n]]\)

    \(\because k\cdot\left|x\right| = n\)\(\left|x\right| \ge 1\)

    \(\therefore k | n\)

    \(x^k = S\),则 \(\forall i \in [1, \dfrac{n}{k} - 1], S[(i - 1)\cdot k + 1..i\cdot k] = S[i\cdot k + 1..(i + 1)\cdot k]\)

    \(S[1..n - k] = S[1..k]^{\dfrac{n}{k} - 1} = S[k + 1..n]\)

    \(\therefore x^k = S \Longrightarrow [k | n] \land [S[1..n - k] = S[k + 1..n]]\)

  • 再证明 \(x^k = S \Longleftarrow [k | n] \land [S[1..n - k] = S[k + 1..n]]\)

    \(\because k | n\)

    \(\therefore k | (n - k)\)

    \(\therefore k \le n - k\)

    \(\because S[1..n - k] = S[k + 1..n]\)\(k \le n - k\)

    \(\therefore S[1..k] = S[k + 1..2k]\)

    以此类推可得 \(S[1..k] = S[k + 1..2k] = S[2k + 1..3k]\cdots\)(严谨证明可用数学归纳法)

    此时有 \(x = S[1..k]\)

    \(\therefore x^k = S \Longleftarrow [k | n] \land [S[1..n - k] = S[k + 1..n]]\)

综上所述,\(x^k = S \Longleftrightarrow [k | n] \land [S[1..n - k] = S[k + 1..n]]\)

假设对于某一个前缀 \(S_i\)\(S[1..i - k] = S[k + 1..i]\),由引理知 \(k\) 即为循环节。

注意到此时 \(i - k \in \pi^{\star}[i]\),题中要求最短周期,则每周期单位长度要最长,即 \(i - k\) 应取 \(\pi[i]\)

还要满足 \(k | i\),即 \((i - \pi[i]) | i\);此时 \(\dfrac{i - \pi[i]}{i}\) 即为最长周期。

喔,\(\pi[i] = 0\) 的情况我们应该跳过。

代码实现

核心部分已用高亮标出。

Code
 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
#include <cstdio>
#define LL long long

const int N = 1e6 + 5;

int n, kase, pi[N];
char S[N];

int main() {
    while(scanf("%d", &n) && n) {
        scanf("%s", S + 1);
        for(int i = 2, k = 0; i <= n; ++i) {
            while(k > 0 && S[k + 1] != S[i])
                k = pi[k];
            if(S[k + 1] == S[i])
                ++k;
            pi[i] = k;
        }
        printf("Test case #%d\n", ++kase);
        for(int i = 2; i <= n; ++i) {
            if(i % (i - pi[i]) == 0 && i != i - pi[i])
                printf("%d %d\n", i, i / (i - pi[i]));
        }
        putchar('\n');
    }
    return 0;
}

  1. 原题链接: Period