問題
$N$ 個の文字列 $S_1, \ldots, S_N$ が与えられる（どの文字列も他の部分文字列でない）。すべての文字列を部分文字列として含む最短の文字列（スーパーストリング）の長さを求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $2 \le N \le 20$ |
| $|S_i|$ | $1 \le |S_i| \le 100$ |
| 文字種 | 英小文字のみ |
| 制限 | 時間 3 sec / メモリ 256MB |
入出力例
入力例 1
4
CATGC
CTAAGT
GCTA
TTCA出力例 1
11例: "GCTAAGTTCATGC" → 長さ 13。最短は 11（最適順序で重複部分を最大化）。
概念図: TSP 型 ビット DP
文字列を「都市」に見立て、辺の重みを「次の文字列を置くときの追加文字数」とした最短 TSP 問題。
ヒント（段階的開示）
ヒント1: 方向性
各文字列を「都市」に見立てた TSP。辺の重み = 「$S_i$ の後に $S_j$ を置くときの追加文字数」= $|S_j| - \text{overlap}(S_i, S_j)$。全文字列を使う最短 Hamiltonian Path を求める。
ヒント2: KMP Overlap 計算
kmp_overlap(a, b) は文字列 b + '#' + a の KMP failure function の最後の値。これが「$a$ の末尾と $b$ の先頭の最大一致長」= overlap(a, b)。$O(|a|+|b|)$ で計算。
ヒント3: DP の遷移コード
INF = 10**9
dp = [[INF]*N for _ in range(1<<N)]
for i in range(N):
dp[1<<i][i] = len(S[i])
for mask in range(1, 1<<N):
for i in range(N):
if dp[mask][i] == INF: continue
if not (mask >> i & 1): continue
for j in range(N):
if mask >> j & 1: continue
new_cost = dp[mask][i] + cost[i][j]
new_mask = mask | (1 << j)
dp[new_mask][j] = min(dp[new_mask][j], new_cost)
print(min(dp[(1<<N)-1]))模範解答 (Python)
import sys
input = sys.stdin.readline
def kmp_overlap(a, b):
"""a の末尾が b の先頭にマッチする最大長 (KMP failure function)"""
s = b + '#' + a
n = len(s)
fail = [0] * n
j = 0
for i in range(1, n):
while j > 0 and s[i] != s[j]:
j = fail[j-1]
if s[i] == s[j]:
j += 1
fail[i] = j
return fail[-1]
def solve():
N = int(input())
S = [input().strip() for _ in range(N)]
ov = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if i != j:
ov[i][j] = kmp_overlap(S[i], S[j])
cost = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
cost[i][j] = len(S[j]) - ov[i][j]
INF = 10**9
FULL = (1 << N) - 1
dp = [[INF]*N for _ in range(1 << N)]
parent = [[-1]*N for _ in range(1 << N)]
for i in range(N):
dp[1 << i][i] = len(S[i])
for mask in range(1, 1 << N):
for i in range(N):
if dp[mask][i] == INF:
continue
if not (mask >> i & 1):
continue
for j in range(N):
if mask >> j & 1:
continue
new_mask = mask | (1 << j)
new_cost = dp[mask][i] + cost[i][j]
if new_cost < dp[new_mask][j]:
dp[new_mask][j] = new_cost
parent[new_mask][j] = i
ans = min(dp[FULL])
print(ans)
# 経路復元
last = dp[FULL].index(ans)
path = []
mask = FULL
while last != -1:
path.append(last)
prev = parent[mask][last]
mask ^= (1 << last)
last = prev
path.reverse()
result = S[path[0]]
for k in range(1, len(path)):
i, j = path[k-1], path[k]
result += S[j][ov[i][j]:]
# print(result) # 文字列自体が必要な場合
solve()
Step-by-Step 解説
1Overlap 計算（KMP）
kmp_overlap(a, b): 文字列 b + '#' + a の failure function の最後の値 = $a$ の末尾と $b$ の先頭の最大一致長。$O(|a|+|b|)$。
2コスト行列
cost[i][j] = |S_j| - overlap[i][j]。$S_i$ の後に $S_j$ を追加するときに増える文字数。
3ビット DP の初期化
dp[1<<i][i] = |S_i|: 各文字列単独から始めた場合の文字数。
4DP の遷移
全 mask, 全 last = i で、未使用の j に対して dp を更新。状態数 $O(2^N \cdot N)$、遷移 $O(N)$、全体 $O(2^N \cdot N^2)$。$N=20$ で約 $4 \times 10^7$。
全 mask, 全 last = i で、未使用の j に対して dp を更新。状態数 $O(2^N \cdot N)$、遷移 $O(N)$、全体 $O(2^N \cdot N^2)$。$N=20$ で約 $4 \times 10^7$。
5経路復元
parent 配列を逆順にたどって文字列の順序を復元。各接続で重複分を除いて結合。
計算量
Overlap 計算: $O(N^2 \cdot L)$ — $L = \max |S_i|$
ビット DP: $O(2^N \cdot N^2)$
経路復元: $O(N)$
合計: $O(2^N \cdot N^2 + N^2 L)$ — $N=20, L=100$ で約 $4 \times 10^7$
ビット DP: $O(2^N \cdot N^2)$
経路復元: $O(N)$
合計: $O(2^N \cdot N^2 + N^2 L)$ — $N=20, L=100$ で約 $4 \times 10^7$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| KMP の文字列順序ミス | a + '#' + b にすると逆 | 必ず b + '#' + a（先頭パターンが b） |
| cost に |S_i| を使う | 追加コストの定義ミス | cost[i][j] = len(S[j]) - ov[i][j] |
| 未使用ビット確認漏れ | 処理済みの文字列に遷移 | if mask >> j & 1: continue を忘れない |
| $N=20$ でメモリ不足 | dp 配列が $2^{20} \times 20 \times 8$ byte ≈ 160MB | int で省メモリ化 or $N \le 20$ を確認 |
次のステップ
- 発展問題: $N \le 25$ への拡張（分割 DP or 近似アルゴリズム）
- 応用: DNA アセンブリ問題（Overlap-Layout-Consensus の核心）
- 理論: セットカバーとの関係（多項式時間近似不可能性・APX-hard）