概要

この問題は、2つのDNA配列（文字列） \(S\) と \(T\) について、一方の末尾と他方の先頭が最大で何文字一致（重なり）できるかを求める問題です。 \(S\) が左・\(T\) が右となる「左側接合」と、\(T\) が左・\(S\) が右となる「右側接合」の2つのパターンにおける最大重なり幅を求め、そのうち大きい方を出力します。

考察

素朴なアプローチとその限界

最も単純な方法は、重なり幅 \(k\) を \(L\) から \(1\) まで順番に試していく方法です。 例えば左側接合の場合、\(S\) の末尾 \(k\) 文字と \(T\) の先頭 \(k\) 文字が一致するかを判定します。 しかし、この方法では一致判定に \(O(k)\) かかるため、全体で \(O(L^2)\) の時間がかかってしまいます。 本問題の制約は \(L, M \le 5 \times 10^5\) であるため、最悪の場合に \(2.5 \times 10^{11}\) 回程度の計算が必要となり、実行時間制限（TLE）になってしまいます。 したがって、より効率的な \(O(L + M)\) のアルゴリズムが必要です。

KMP法（LPS配列）の応用

文字列の「接頭辞（先頭部分）」と「接尾辞（末尾部分）」が一致する最長の高さを高速に求める手法として、KMP法（Knuth-Morris-Pratt Algorithm）のLPS（Longest Prefix Suffix）配列の構築アルゴリズムが利用できます。

LPS配列とは、ある文字列の各位置において、「接頭辞であり、かつ接尾辞でもある最長の部分文字列の長さ（自分自身は除く）」を記録した配列です。文字列全体のLPS配列は、文字列の長さを \(N\) とすると \(O(N)\) の線形時間で構築できます。

この性質を本問題にうまく応用します。

1. 左側接合（\(S\) の末尾と \(T\) の先頭の重ね合わせ） \(T\) の先頭（接頭辞）と \(S\) の末尾（接尾辞）の一致を調べたいため、2つの文字列を特殊な区切り文字 # を挟んで連結した文字列 \(P_1 = T + \text{"\#"} + S\) を作成します。 この \(P_1\) に対してLPS配列を構築すると、末尾の要素の値が「\(P_1\) 全体の接頭辞（\(T\) の先頭から始まる）であり、かつ接尾辞（\(S\) の末尾で終わる）である最長の一致長さ」となり、これが左側接合の最大重なり幅になります。

2. 右側接合（\(T\) の末尾と \(S\) の先頭の重ね合わせ） 同様に、\(P_2 = S + \text{"\#"} + T\) という文字列を作成し、LPS配列を構築することで、右側接合の最大重なり幅を求めることができます。

アルゴリズム

KMP法のLPS配列構築

文字列 pattern に対するLPS配列 lps を以下のように構築します。

1. lps 配列を 0 で初期化します。
2. 2つのポインタ i（探索位置、1から開始）と j（一致している接頭辞の長さ、0から開始）を用意します。
3. i を右に動かしながら、以下を繰り返します：
   • pattern[i] と pattern[j] が一致しない場合、一致する可能性がある短い接頭辞まで j を戻します（j = lps[j-1]）。これを一致するか j = 0 になるまで繰り返します。
   • pattern[i] と pattern[j] が一致する場合、j を 1 進めます。
   • lps[i] に j の値を記録します。

具体例

\(S = \text{"101"}\), \(T = \text{"0110"}\) の左側接合を考えます。 連結文字列は \(P_1 = T + \text{"\#"} + S = \text{"0110\#101"}\) となります。

この文字列に対するLPS配列の計算過程は以下のようになります：

インデックス i	文字 P_1[i]	lps[i] の値	説明
0	0	0	先頭文字
1	1	0	一致なし
2	1	0	一致なし
3	0	1	接頭辞 "0" と接尾辞 "0" が一致
4	#	0	区切り文字のため一致なし
5	1	0	一致なし
6	0	1	接頭辞 "0" と接尾辞 "0" が一致
7	1	2	接頭辞 "01" と接尾辞 "01" が一致

末尾の lps[7] の値は 2 となり、最大重なり幅が 2（\(S\) の末尾 "01" と \(T\) の先頭 "01" が一致）であることが \(O(L+M)\) で求まります。

計算量

• 時間計算量: \(O(L + M)\) 長さ \(L + M + 1\) の文字列に対するLPS配列の構築は、ポインタ i が右に進む回数と j が戻る回数の合計が高々文字数の2倍に抑えられるため、線形時間 \(O(L + M)\) で動作します。これを左側接合と右側接合の2回行うため、全体の計算量も \(O(L + M)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(L + M)\) 連結した文字列 \(P_1, P_2\) およびそれに対応する長さ \(L + M + 1\) のLPS配列を保持するため、空間計算量は \(O(L + M)\) となります。

実装のポイント

• 区切り文字 "#" の重要性 もし区切り文字を挟まずに \(T + S\) としてしまうと、重なり幅が \(S\) の長さ \(L\) を超えて \(T\) の内部までマッチしてしまう可能性があります（例えば \(S\) が \(T\) の完全な部分文字列である場合など）。 問題の定義上、接合は端同士で行うため、重なり幅は最大でも \(L\)（\(S\) の長さ）以下でなければなりません。 \(S\) や \(T\) には絶対に出現しない文字 "#" を間に挟むことで、LPSの探索が "#" を超えて一致することを防ぎ、正しく「端同士の重なり（最大 \(L\)）」のみを検出することができます。

  ソースコード

import sys

def solve():
    # 入力の高速読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    L = int(input_data[0])
    M = int(input_data[1])
    S = input_data[2]
    T = input_data[3]
    
    # KMP法を用いて、pattern の最長自明でない接頭辞かつ接尾辞の長さを求める
    def get_max_overlap(pattern):
        n = len(pattern)
        lps = [0] * n
        j = 0
        for i in range(1, n):
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            lps[i] = j
        return lps[-1]

    # 左側接合: S の末尾 k 文字 と T の先頭 k 文字の一致 (T + '#' + S)
    # 右側接合: T の末尾 k 文字 と S の先頭 k 文字の一致 (S + '#' + T)
    ans1 = get_max_overlap(T + '#' + S)
    ans2 = get_max_overlap(S + '#' + T)
    
    print(max(ans1, ans2))

if __name__ == '__main__':
    solve()

---

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