解題說明
Greatest Common Divisor of Strings
題目描述：對兩個字串 str1 和 str2，若存在字串 x 使得 str1 和 str2 都是由 x 重複若干次拼接而成，則稱 x 能「整除」兩者。求最長的這樣的 x。
解題思路：先做合法性驗證：若 str1 + str2 != str2 + str1，則不存在公因子字串，直接回傳空字串。這個等式成立是存在公因字串的充要條件——因為若兩者都由同一模式 t 生成，則拼接順序不影響結果。
驗證通過後，答案的長度就是 len(str1) 和 len(str2) 的最大公因數（GCD）。最長公因字串即 str1 的前 gcd(len1, len2) 個字元。這是將整數 GCD 概念優雅地推廣到字串領域的經典例子。
C++ 解法
複雜度分析
時間複雜度：O(n + m) — 字串拼接比較需 O(n + m)，其中 n = len(str1)，m = len(str2)；GCD 計算 O(log(min(n, m)))。
空間複雜度：O(n + m) — 暫存拼接字串所需空間。
虛擬碼
1. If str1 + str2 != str2 + str1: return "" 2. Compute g = gcd(len(str1), len(str2)) 3. Return str1[0..g-1]
其他解法
暴力枚舉：枚舉所有可能的因子長度（從 min(len1, len2) 到 1 的因子），逐一驗證是否能整除兩個字串。時間複雜度 O((n+m) * d(min(n,m)))，其中 d 為因子個數，比 GCD 方法慢。
KMP 最長公共前綴：找兩字串最長公共前綴，再驗證其能否整除兩字串。正確但實作複雜度高於直接用 GCD。
延伸思考
- 如何證明「str1 + str2 == str2 + str1」是存在公因字串的充要條件？
- 此題能推廣至三個字串嗎？如何求三個字串的最大公因子字串？
- 若允許字元重排（anagram），最長公因字串的長度如何計算？