LA 3026 Period 完整解析

對字串 S 的每個前綴（長度 2~N），判斷是否為週期字串（即 A^K, K>1）。若是，輸出長度與最大 K。N ≤ 1,000,000。

核心洞察：KMP 失效函數直接給出週期

KMP fail[i] = 長度為 i 的前綴最長真前綴後綴長度。
若 i % (i - fail[i]) == 0 且 fail[i] > 0，則前綴由長度 i - fail[i] 的子串重複 K = i / (i - fail[i]) 次構成。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000010;
int fail[MAXN];
char s[MAXN];

void build_fail() {
    int n = strlen(s);
    fail[0] = fail[1] = 0;
    for (int i = 1; i < n; i++) {
        int j = fail[i];
        while (j && s[i] != s[j]) j = fail[j];
        fail[i+1] = (s[i] == s[j]) ? j + 1 : 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, tc = 0;
    while (cin >> n >> s, n) {
        build_fail();
        cout << "Test case #" << ++tc << '\n';
        for (int i = 2; i <= n; i++) {
            int period = i - fail[i];
            if (i % period == 0 && fail[i] > 0)
                cout << i << ' ' << i / period << '\n';
        }
        cout << '\n';
    }
    return 0;
}

範例驗證

輸入：
3
aaa
12
aabaabaabaab
0

輸出：
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4

關鍵點總結

• KMP fail 陣列：fail[i] 表示長度 i 前綴的最長邊界長度
• 週期判定條件：i % (i - fail[i]) == 0 且 fail[i] > 0
• 線性時間：KMP 建立 O(N)，查詢 O(N)，總 O(N)
• 輸出格式：測試用例編號、空行分隔