ZJANS

a223. 10298 - Power Strings

Medium Last Update: 2025/08/30
KMP

# 題目簡述

解法一、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

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

驗證 s.size() / l 是否能整除
否則最大重複次數 = 1

s = "AAABAAAB"

以 s = "AAABAAAB" 舉例

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

A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
0
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
01
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
012
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
0120
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
01201
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
012012
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
0120123
A
A		A
A		A
A		B
B		A
A		A
A		A
A		B
B
01201234

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

重複次數為
s.size() / l = 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() 因數的 重複字串長度 才能讓 字串重複次數 是整數
接著對每個位置判斷是否相同 (bool check(int size))

s = "AAABAAAB"

以 s = "AAABAAAB" 舉例

s.size() = 8
可能的 重複字串的長度 l 為 1, 2, 4
如果假設正確 s[i] 經過 l 個字符後會再重複一次 (還會是s[i])
因此檢查每個位置是否都符合 s[i] == s[i+l]

假設 l = 1
s[0] == s[0+1] 符合
s[1] == s[1+1] 符合
s[2] == s[2+1] 不符合 (return false)

假設 l = 2
s[0] == s[0+2] 符合
s[1] == s[1+2] 不符合 (return false)

假設 l = 4
s[0] == s[0+4] 符合
s[1] == s[1+4] 符合
s[2] == s[2+4] 符合
s[3] == s[3+4] 符合

所以取 l = 4

✅ 完整代碼

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

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

string s;

bool check(int l){
    for(int i=0; i<s.size()-l; i++){
        if(s[i] != s[i+l]) 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;
}