火星探測資料 (APCS 2026-11 中高級)

探測車在火星表面做了 \(k\) 次探測，每次的結果都記成一個長度為 \(n\)、只含小寫英文字母的字串。這些資料要傳回地球，而每多傳一個字母就要多耗一點能源，所以研究團隊決定只傳一個字串 \(S\) 回去，用它來涵蓋全部 \(k\) 筆結果。

\(S\) 要滿足的條件是：任何一筆探測結果都是 \(S\) 的連續子字串。不同筆結果在 \(S\) 裡可以共用一部分字母，出現的先後也不必照輸入的順序；如果有好幾筆結果一模一樣，它們在 \(S\) 中出現一次就夠了。例如 rock 與 ocks 可以合併成 rocks，不必寫成 rockocks。

請找出長度最短的 \(S\)。如果長度最短的 \(S\) 不只一個，請輸出其中字典序最小的那一個。

• 連續子字串：從 \(S\) 中取出一段相鄰的字元、順序不變，得到的字串就是 \(S\) 的連續子字串。例如 lan 是 planet 的連續子字串；pnt 則不是，因為 p、n、t 在 planet 裡並不相鄰。
• 字典序：兩個長度相同的字串，由左往右逐字比較，第一個不一樣的位置上，字母在字母表中排得比較前面的那個字串，字典序比較小。例如 rocker 和 rocket 的前五個字母都相同，第六個字母 r 排在 t 前面，所以 rocker 的字典序比 rocket 小。

輸入格式

第一行有兩個正整數 \(n\)、\(k\)：\(n\) 是每筆探測結果的字母數，\(k\) 是探測結果有幾筆。

之後的 \(k\) 行各有一個字串，依序是第 \(1\) 筆到第 \(k\) 筆探測結果。

限制

• \(1 \le n \le 8\)
• \(1 \le k \le 9\)
• 每筆探測結果的長度恰好是 \(n\)，而且只由小寫英文字母 a～z 組成

輸出格式

輸出一行，為長度最短的 \(S\)；長度最短的 \(S\) 不只一個時，輸出字典序最小的那一個。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

4 2
aaaa
bbbb

範例輸出 1

aaaabbbb

範例解釋 1

aaaa 只含字母 a，bbbb 只含字母 b，兩者沒有任何部分能重疊，所以 \(S\) 至少要有 \(4 + 4 = 8\) 個字母。長度為 \(8\) 而且同時包含這兩筆的字串只有 aaaabbbb 和 bbbbaaaa，兩者的第一個字母分別是 a 和 b，所以答案是 aaaabbbb。

範例輸入 2

4 6
aaaa
aaab
aaba
aabc
abaa
baaa

範例輸出 2

aabaaaabc

範例解釋 2

把六筆探測結果對齊到它們在答案中出現的位置：

aabaaaabc
aaba
 abaa
  baaa
   aaaa
    aaab
     aabc

把六筆排成 aaba → abaa → baaa → aaaa → aaab → aabc，相鄰兩筆都重疊 \(3\) 個字母（後一筆開頭的 \(3\) 個字母就是前一筆結尾的 \(3\) 個字母），一路接下去恰好是 aabaaaabc。

這已經是最短的：六筆探測結果互不相同，在 \(S\) 中必須從六個不同的位置開始；而長度為 \(8\) 的字串裡，長度為 \(4\) 的連續子字串只能從第 \(1\)～\(5\) 個位置開始，不夠放六筆，所以 \(S\) 至少要有 \(9\) 個字母。事實上，長度為 \(9\) 而且包含全部六筆的字串只有 aabaaaabc 這一個。

題目來源

APCS 2026 年 11 月中高級實作題第 2 題。

官方未公布題本，題敘參考 ecc〈APCS 2026 11月中高級〉 整理，細節可能與正式試題有出入。