解法一、KMP

🔹 最長公共前後綴

開一個大小為 s.size() 的矩陣 kmp[]
其中 kmp[i] 紀錄的是 s[0] ~ s[i] 的 最長起始位置不同的前後綴字串 的長度

初始化 kmp[0] = 0 (s[0] 跟 s[0] 起始位置相同)
如果 s[i] = s[kmp[i-1]] 則 kmp[i] = kmp[i-1] + 1
否則 kmp[i] = 0

最短重複子字串長度 = s.size() - kmp.back()
最大重複次數 = s.size() / 重複子字串長度

驗證 s.size() / 重複子字串長度 能整除
否則最大重複次數 = 1

🔸 e.g. s = "AAABAAAB"

綠字 表示 最長起始位置不同的前後綴字串
紅字 代表匹配錯誤 (kmp[i] = 0)
底下的數字是字串長度 (kmp[i])

因此 AAABAAAB 最短重複子字串長度為
s.size() - kmp.back() = 4

重複次數為
s.size() / 重複子字串長度 = 2

✅ 完整代碼

評分結果(參考) ： AC (0.1s, 9.8MB)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    while (cin >> s && s != ".") {
        int size = s.size();

        vector<int> kmp(size);
        for(int i=1; i<size; i++){
            int j = kmp[i-1];
            while(j>0 && s[i]!=s[j]){
                j = kmp[j - 1];
            }
            if(s[i] == s[j]){
                j++;
            }
            kmp[i] = j;
        }
    
        int p = size - kmp.back(); // period

        if(size%p == 0){
            cout << size/p << "\n";
        }
        else{
            cout << 1 << "\n";
        }
    }

    return 0;
}

解法二、窮舉

🔹 窮舉因數

窮舉重複字串可能的長度
只有長度是 s.size() 的因數的 重複字串長度 才能讓 字串重複次數 是整數
然後對每個位置判斷是否相同

✅ 完整代碼

評分結果(參考) ： AC (44ms, 2.2MB)

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

string s;

bool check(int size){
    for(int i=size; i<s.size(); i++){
        if(s[i] != s[i-size]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> s && s != ".") {
        int ans = 1;
        int size = s.size();

        for(int i=1; i<=size/2; i++){
            if(size%i != 0) continue;
            
            if(check(i)){
                ans = size/i;
                break;
            }
        }
    
        cout << ans << "\n";
    }

    return 0;
}