周期

AcWing-141-周期

分析

见《进阶指南》第74页。

实现

#include <iostream>
#define next NeXt
using namespace std;

const int N = 1000010;
int n;
char str[N];
int next[N];

void get_next_array () {
    next[1] = 0;
    for (int i = 2, j = 0; i <= n; ++ i) {
        while (j > 0 && str[i] != str[j + 1]) j = next[j];
        if (str[i] == str[j + 1]) ++ j;
        next[i] = j;
    }
}

int main () {
    int T = 0;
    while (scanf("%d", &n) && n) {
        scanf("%s", str + 1);

        get_next_array();
        printf("Test case #%d\n", ++ T);
        for (int i = 2; i <= n; ++ i)
            if (i % (i - next[i]) == 0 && i / (i - next[i]) >= 2)
                printf("%d %d\n", i, i / (i - next[i]));
        printf("\n");
    }
    return 0;
}