概要

\(N\) 枚の看板を順番につなげる際、隣り合う看板同士で「前の看板の末尾」と「次の看板の先頭」が一致する部分を最大限重ねて配置し、横断幕全体の総文字数を求める問題です。

考察

重要な気づき

隣り合う2つの文字列 \(S_{i-1}\) と \(S_i\) について、\(S_{i-1}\) の末尾 \(l\) 文字と \(S_i\) の先頭 \(l\) 文字が一致する最大の \(l\) を求めたい。これは言い換えると、「\(S_{i-1}\) の接尾辞(suffix)であり、かつ \(S_i\) の接頭辞(prefix)でもある」最長の文字列の長さを求める問題です。

素朴なアプローチの問題点

単純に全ての \(l\) を試して文字列比較すると、各ペアについて \(O(\min(|S_{i-1}|, |S_i|)^2)\) かかり、文字列が長い場合にTLEになります。

解決策

KMP法（Knuth-Morris-Pratt法）を利用します。\(S_i\) を「パターン」として、\(S_{i-1}\) を「テキスト」として KMP マッチングを実行すると、\(S_{i-1}\) の末尾まで走査し終わった時点でのマッチ長が、求めたい最大重なり長さに対応します。

アルゴリズム

KMP法による最大重なりの計算

1. 失敗関数(failure function)の構築: \(S_i\)（パターン）に対して KMP の失敗関数を計算する。失敗関数 \(\text{fail}[j]\) は「\(S_i\) の先頭 \(j+1\) 文字の、最長の “接頭辞かつ接尾辞” の長さ」を表す。

2. KMPマッチングの実行: \(S_{i-1}\)（テキスト）を左から右に走査し、\(S_i\) とのマッチングを進める。テキストの最後まで到達した時点のマッチ長 \(k\) が、\(S_{i-1}\) の末尾と \(S_i\) の先頭が一致する最長の長さとなる。

3. 制約の処理:

   • \(k = |S_i|\)（完全一致）の場合、\(l < |S_i|\) の制約に違反するので、\(k = \text{fail}[k-1]\) に戻す。
   • \(k \geq |S_{i-1}|\) の場合、\(l < |S_{i-1}|\) の制約に違反するので、同様に失敗関数で戻す。

具体例

\(S_1 = \) abcabc, \(S_2 = \) abcxyz の場合：

• \(S_2\) の失敗関数を構築: [0, 0, 0, 0, 0, 0]
• \(S_1\) に対して KMP マッチング実行:
  • a → \(k=1\), b → \(k=2\), c → \(k=3\), a → \(k=1\)（xと不一致で戻って再マッチ）…
  • 実際には abcabc の末尾3文字 abc が \(S_2\) の先頭 abc と一致し、\(k=3\)
• \(L_2 = 3\), 総文字数 \(= 6 + (6 - 3) = 9\)

総文字数の計算

\[\text{総文字数} = |S_1| + \sum_{i=2}^{N} (|S_i| - L_i)\]

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} |S_i|\right)\)
  • 各ペア \((S_{i-1}, S_i)\) に対して、KMP の失敗関数構築に \(O(|S_i|)\)、マッチングに \(O(|S_{i-1}|)\) かかる。全体では各文字列が最大2回（テキストとして1回、パターンとして1回）使われるので、合計は文字列長の総和に比例。
• 空間計算量: \(O\left(\max_i |S_i|\right)\)（失敗関数の配列）

実装のポイント

• 完全一致のハンドリング: KMP マッチング中にパターンが完全一致した場合（\(k = |S_i|\)）、\(l < |S_i|\) の制約があるため \(k = \text{fail}[k-1]\) で次に長いマッチ長に戻す必要がある。

• \(l < |S_{i-1}|\) の制約: マッチング完了後、\(k \geq |S_{i-1}|\) の場合も失敗関数で巻き戻して制約を満たす最大値を見つける。

• 入力の高速化: Python では sys.stdin.buffer.read() を使って入力を一括読み込みすることで I/O のオーバーヘッドを削減する。

  ソースコード

import sys

def compute_kmp_failure(pattern):
    m = len(pattern)
    fail = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[k] != pattern[i]:
            k = fail[k - 1]
        if pattern[k] == pattern[i]:
            k += 1
        fail[i] = k
    return fail

def find_max_overlap(s_prev, s_curr):
    # We want the longest l such that:
    # 1 <= l < len(s_prev) and l < len(s_curr)
    # s_prev ends with s_curr[:l]
    # We use KMP: treat s_curr as "pattern" and match against s_prev
    # But we only care about the suffix of s_prev matching a prefix of s_curr.
    
    # Build KMP failure function for s_curr
    # Then run KMP matching of s_curr against s_prev, and at the end of s_prev,
    # the current match length gives us the longest prefix of s_curr that matches
    # a suffix of s_prev.
    
    len_prev = len(s_prev)
    len_curr = len(s_curr)
    
    if len_prev == 0 or len_curr == 0:
        return 0
    
    # Build failure function for s_curr
    fail = compute_kmp_failure(s_curr)
    
    # Run KMP: match s_curr (as pattern) against s_prev (as text)
    k = 0  # number of characters of s_curr matched so far
    for i in range(len_prev):
        while k > 0 and s_curr[k] != s_prev[i]:
            k = fail[k - 1]
        if s_curr[k] == s_prev[i]:
            k += 1
        if k == len_curr:
            # Full match of s_curr found in s_prev; we need to back off
            # because l < len_curr is required
            k = fail[k - 1]
    
    # k is the length of the longest prefix of s_curr that matches
    # a suffix of s_prev. But we also need l < len_prev.
    # k < len_curr is guaranteed (we handled full match above).
    # We need k < len_prev as well.
    while k >= len_prev:
        if k == 0:
            break
        k = fail[k - 1]
    
    return k

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    
    strings = []
    for i in range(N):
        strings.append(tokens[idx]); idx += 1
    
    total = len(strings[0])
    for i in range(1, N):
        overlap = find_max_overlap(strings[i-1], strings[i])
        total += len(strings[i]) - overlap
    
    print(total)

if __name__ == '__main__':
    main()

---

この解説は claude4.6opus-thinking によって生成されました。