概要

この問題は、隣り合う2つの文字列 \(S_{i-1}\) と \(S_i\) について、「\(S_{i-1}\) の末尾」と「\(S_i\) の先頭」が一致する最大の長さ \(L_i\) を高速に求める問題です。ただし、どちらの文字列も完全には重ねられないという制約（\(L_i < |S_{i-1}|\) かつ \(L_i < |S_i|\)）を満たす必要があります。

考察

愚直な方法とその限界

各隣り合うペア \((S_{i-1}, S_i)\) について、重ね合わせる長さ \(l\) を大きい方から順に試し、文字列の比較を行う方法が考えられます。 しかし、文字列の総長 \(\sum |S_i| \leq 10^6\) であるため、最悪の場合（例えば aaaa...aa のような同じ文字が続く場合）に1ペアの比較だけで \(O(|S_{i-1}| \cdot |S_i|)\) の時間がかかってしまい、実行時間制限（TLE）になってしまいます。

したがって、各ペアの重ね合わせの長さを、文字列の長さに比例する時間（線形時間）で求める必要があります。

KMP（Knuth-Morris-Pratt）アルゴリズムの応用

「ある文字列の末尾」と「別の文字列の先頭」の一致を高速に判定する問題は、文字列検索アルゴリズムである KMP法 を応用することで高速に解くことができます。

KMP法では、パターン文字列 \(B\)（ここでは \(S_i\)）に対して、\(\pi\) テーブル（プレフィックス関数） を事前に構築します。\(\pi\) テーブルの \(j\) 番目の値は、「\(B\) の先頭 \(j+1\) 文字の部分文字列において、接頭辞（prefix）と接尾辞（suffix）が一致する最長の一致長」を表します。

これを利用して、テキスト \(A\)（ここでは \(S_{i-1}\)）に対してパターン \(B\) のマッチングを行います。\(A\) の最後まで走査した時点でのマッチングの長さ j_match は、まさに「\(A\) の末尾」と「\(B\) の先頭」が一致する最大の長さを表すことになります。

重なりの制約の処理

問題文には以下の制約があります。 - \(l < |S_{i-1}|\) （\(S_{i-1}\) 全体が重なってはいけない） - \(l < |S_i|\) （\(S_i\) 全体が重なってはいけない）

KMPマッチングによって得られた最大の一致長 j_match が、これらの制約に引っかかる場合は、\(\pi\) テーブルを利用して「次に長い一致長」へ巻き戻す必要があります。 - j_match == |S_i| の場合、j_match = pi[j_match - 1] と更新する。 - j_match == |S_{i-1}| の場合、j_match = pi[j_match - 1] と更新する。

これにより、制約を満たす正しい最大重なり長 \(L_i\) を \(O(|S_{i-1}| + |S_i|)\) で求めることができます。

アルゴリズム

各隣り合う看板のペア \(A = S_{i-1}, B = S_i\) に対して以下の処理を行います。

1. \(B\) の \(\pi\) テーブル構築: \(B\) のプレフィックス関数 pi を構築します。
2. \(A\) に対する \(B\) のマッチング: KMP法を用いて、\(A\) の各文字を走査しながら \(B\) とのマッチング長 j_match を更新します。 走査の途中で j_match が \(B\) の長さ（len_B）に達した場合は、完全一致（\(l = |S_i|\)）を避けるために pi テーブルを使ってマッチング長を戻します。
3. 境界条件のチェック: \(A\) の走査が終了した時点で、j_match が \(A\) の長さ（len_A）に達している場合も、完全一致（\(l = |S_{i-1}|\)）を避けるために pi テーブルを使ってマッチング長を戻します。
4. 総文字数の更新: 最終的な j_match が \(L_i\) となります。全体の長さに \(B\) の新たに加わる長さ len_B - j_match を加算します。

計算量

• 時間計算量: \(O(\sum_{i=1}^{N} |S_i|)\) 各ステップ \(i\) において、\(\pi\) テーブルの構築に \(O(|S_i|)\)、KMPマッチングに \(O(|S_{i-1}|)\) の時間がかかります。これらをすべての \(i\) について足し合わせると、文字列の総長に対する線形時間となるため、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(\max |S_i|)\) 各ステップで保持する \(\pi\) テーブルのサイズは最大でも \(\max |S_i|\) です。これを毎回再利用または解放するため、メモリ使用量は非常に小さく抑えられます。

実装のポイント

• KMPの巻き戻し: while j_match > 0 and A[j] != B[j_match]: の部分で、文字が不一致のときに pi テーブルを使ってマッチング位置を効率的に戻しています。これにより、無駄な比較を省いて高速化を達成しています。

• 完全一致の回避: j_match == len_B と j_match == len_A の境界条件の処理を正しく行うことで、「看板全体がもう一方の看板に完全に吸い込まれてしまう」ケースを正しく排除しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    S = input_data[1:]
    
    total_len = len(S[0])
    
    for i in range(1, N):
        A = S[i-1]
        B = S[i]
        
        len_A = len(A)
        len_B = len(B)
        
        # B の pi テーブル構築
        pi = [0] * len_B
        for j in range(1, len_B):
            k = pi[j-1]
            while k > 0 and B[j] != B[k]:
                k = pi[k-1]
            if B[j] == B[k]:
                k += 1
            pi[j] = k
            
        # A の走査
        j_match = 0
        for j in range(len_A):
            while j_match > 0 and A[j] != B[j_match]:
                j_match = pi[j_match-1]
            if A[j] == B[j_match]:
                j_match += 1
            if j_match == len_B:
                j_match = pi[j_match-1]
                
        if j_match == len_A:
            j_match = pi[j_match-1]
            
        total_len += len_B - j_match
        
    print(total_len)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。