Period：KMP 求字符串所有前綴的周期

題目大意

對字符串 S 的每個前綴（長度 i=2..N），若其可表示為某子串 A 重複 K 次（K>1），輸出 i 和 K。N ≤ 1,000,000。

KMP next 數組性質

對前綴長度 i，其最小循環節長度 t = i - next[i]。若 i % t == 0 且 i/t > 1，則周期 K = i/t。

代碼實現

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1000005;
char s[MAXN];
int nxt[MAXN];

void getNext() {
    int n = strlen(s);
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < n) {
        if (j == -1 || s[i] == s[j]) nxt[++i] = ++j;
        else j = nxt[j];
    }
}

int main() {
    int cas = 1;
    while (true) {
        int n; scanf("%d", &n);
        if (n == 0) break;
        scanf("%s", s);
        getNext();
        printf("Test case #%d\n", cas++);
        for (int i = 2; i <= n; i++) {
            int t = i - nxt[i];
            if (i % t == 0 && i / t > 1)
                printf("%d %d\n", i, i / t);
        }
        printf("\n");
    }
    return 0;
}

關鍵點

• next 數組下標從 0 或 1 開始需一致。代碼中 nxt[i] 對應長度 i 的前綴最長公共前後綴長度。
• 輸出格式：每測試案例先輸出 "Test case #x"，再每行一對 "i K"，最後空行。
• 時間 O(N) 每測試案例，滿足百萬級數據。

總結

KMP next 數組不僅用於模式匹配，其值直接給出每個前綴的最小周期長度。本題是 KMP 經典應用：線性掃描輸出所有有周期的前綴。