概要

文字列 \(S\) と \(T\) を「1文字以上重ねて」接合するとき、左側接合（\(S\)→\(T\)）・右側接合（\(T\)→\(S\)）それぞれで可能な重なり幅 \(k\) の最大値を求めます。

考察

接合で必要なのは「端同士の一致」です。

• 左側接合: \(S\) の末尾 \(k\) 文字 ＝ \(T\) の先頭 \(k\) 文字
  → 「\(S\) の各 suffix が \(T\) の prefix とどこまで一致するか」を調べればよい
• 右側接合: \(T\) の末尾 \(k\) 文字 ＝ \(S\) の先頭 \(k\) 文字
  → 「\(T\) の各 suffix が \(S\) の prefix とどこまで一致するか」を調べればよい（ただし \(k\le L\)）

素朴に \(k=1..L\) を全部試して比較すると、各比較が最悪 \(O(L)\) かかるため全体で \(O(L^2)\) になり、\(L\le 5\times 10^5\) では間に合いません。

そこで「ある文字列の prefix と、別の場所から始まる部分文字列の最長共通接頭辞（LCP）」を一括で高速に求められる Zアルゴリズムを使って、全体を \(O(L+M)\) にします。

アルゴリズム

1. Zアルゴリズムとは

文字列 \(P\) に対して配列 \(Z\) を作り、 - \(Z[i]\) = \(P[0:]\)（全体の先頭）と \(P[i:]\) が先頭から何文字一致するか
を全ての \(i\) について \(O(|P|)\) で求めます。

2. 左側接合（\(S\) の suffix と \(T\) の prefix）

求めたいのは最大の \(k\)（\(1\le k\le L\)）で - \(S[L-k:] = T[:k]\)

これを「\(T\) の prefix と、\(S\) の各 suffix の一致長」として見るために - \(P = T + \text{sep} + S\)（sep は 0,1 に存在しない区切り文字として 2 を使用） を作って Z 配列を計算します。

\(S\) の位置 pos（\(0\le pos < L\)）から始まる suffix の長さは - \(\text{need} = L - pos\)

\(P\) 上でその suffix の開始位置は i = (M+1) + pos なので、 - \(Z[i] \ge \text{need}\) なら、\(T\) の先頭 \(\text{need}\) 文字と \(S[pos:]\) が一致
→ 重なり幅 \(k=\text{need}\) の左側接合が可能

これを全 pos について見て最大の \(\text{need}\) を left_max にします。

3. 右側接合（\(T\) の suffix と \(S\) の prefix）

求めたいのは最大の \(k\)（\(1\le k\le L\)）で - \(T[M-k:] = S[:k]\)

今度は \(S\) の prefix と \(T\) の各 suffix を比較したいので - \(P2 = S + \text{sep} + T\) を作って Z 配列を計算します。

\(T\) の位置 pos（\(0\le pos < M\)）から始まる suffix の長さは - \(\text{need} = M - pos\)

\(P2\) 上でその suffix の開始位置は i = (L+1) + pos なので、 - \(Z2[i] \ge \text{need}\) なら、\(S\) の先頭 \(\text{need}\) 文字と \(T[pos:]\) が一致
→ 重なり幅 \(k=\text{need}\) の右側接合が可能

ただし条件として \(k\le L\) なので、見るべきは \(\text{need}\le L\) の suffix のみです。
これは pos >= M-L（長さ \(L\) 以内の suffix）に対応するため、コードでは - start_pos = M - L から走査しています。

最後に max(left_max, right_max) が答えで、どちらも 1 以上が無理なら 0 を出力します。

計算量

• 時間計算量: \(O(L+M)\)
  （Zアルゴリズムを長さ \(L+M+1\) の文字列に対して2回実行）
• 空間計算量: \(O(L+M)\)
  （結合文字列と Z 配列）

実装のポイント

• 区切り文字 sep は 0 と 1 に含まれない文字を使う必要があります（ここでは '2'）。これにより、\(T\) と \(S\)（または \(S\) と \(T\)）の境界をまたいだ誤一致を防げます。

• 左側接合では「\(S\) の各 suffix（長さ \(L-pos\)）」を全探索し、z[i] >= need なら成立。

• 右側接合では「\(T\) の suffix のうち長さ \(\le L\) のもの」だけを見ればよいので、pos の開始を M-L にして無駄を減らしています。

• 「重なりなし連結は禁止」なので、最終的に \(k\ge 1\) が存在しない場合は 0 を出力します。

  ソースコード

import sys

def z_algorithm(s: str):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            k = i - l
            zi = z[k]
            if i + zi < r:
                z[i] = zi
                continue
            j = r - i
        else:
            j = 0
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j
        if i + j > r:
            l, r = i, i + j
    return z

def main():
    input = sys.stdin.readline
    L, M = map(int, input().split())
    S = input().strip()
    T = input().strip()

    sep = '2'

    # Left join: suffix of S matches prefix of T
    P = T + sep + S
    z = z_algorithm(P)
    base = M + 1
    left_max = 0
    for i in range(base, len(P)):
        pos = i - base
        need = L - pos  # length of suffix starting at pos
        if need <= 0:
            continue
        if z[i] >= need:
            if need > left_max:
                left_max = need

    # Right join: suffix of T matches prefix of S
    P2 = S + sep + T
    z2 = z_algorithm(P2)
    base2 = L + 1
    right_max = 0
    start_pos = max(0, M - L)  # only suffixes of length <= L
    for i in range(base2 + start_pos, len(P2)):
        pos = i - base2
        need = M - pos  # length of suffix starting at pos
        if need <= 0 or need > L:
            continue
        if z2[i] >= need:
            if need > right_max:
                right_max = need

    ans = max(left_max, right_max)
    if ans < 1:
        ans = 0
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。