解題說明
Repeated String Match
題目描述：給定兩個字串 a 和 b，求最少需要重複 a 多少次才能讓 b 成為重複後字串的子串。若不可能則回傳 -1。
解題思路：首先確認 b 中的所有字元都出現在 a 中，否則直接回傳 -1。然後計算最少需要重複的次數：至少需要 ceil(len(b) / len(a)) 次才能覆蓋 b 的長度。由於 b 的起始位置可能不對齊 a 的開頭，還需要最多多重複一次。因此只需檢查重複 k 次和 k+1 次（其中 k = ceil(len(b)/len(a))）是否包含 b 即可。使用 KMP 或內建的 find 函式進行子串匹配。
C++ 解法
複雜度分析
時間複雜度：O(n + m) — 其中 n = k * len(a)（重複後的字串長度），m = len(b)。使用 KMP 或 Rabin-Karp 可達線性子串匹配。內建 find 最壞 O(n * m)。
空間複雜度：O(n) — 重複後的字串佔用 O(k * len(a)) 空間。
虛擬碼
1. Compute k = ceil(len(b) / len(a)) 2. Build repeated string = a repeated k times 3. If b is a substring of repeated, return k 4. Append one more copy of a to repeated 5. If b is a substring of repeated, return k + 1 6. Return -1
其他解法
Rabin-Karp 滾動雜湊：不實際建構重複字串，而是模擬無限重複 a 的過程，用 Rabin-Karp 滾動雜湊比對 b。空間 O(m) 且避免大字串拼接，但實作更複雜。
KMP 匹配：對 b 建立 KMP failure function，然後在「虛擬」的重複 a 上進行 KMP 匹配（用 i % len(a) 取字元）。時間 O(k*len(a) + len(b))，無需實際拼接字串。
延伸思考
- 為什麼最多只需要多重複一次（k+1 次而非更多）？能否給出嚴格的上界證明？
- 如果 a 和 b 非常長，如何避免建構完整的重複字串來節省記憶體？
- 此問題與字串的週期性（periodic string）有何關聯？