概要

2つの文字列 \(S\)（長さ \(L\)）と \(T\)（長さ \(M\)）が与えられます。\(S\) の末尾と \(T\) の先頭を重ね合わせる「左側接合」と、\(T\) の末尾と \(S\) の先頭を重ね合わせる「右側接合」の2通りについて、重ね合わせられる最大の長さ（重なり幅）を求め、そのうちの最大値を出力する問題です。

考察

素朴なアプローチ（ナイーブな比較）

重なり幅 \(k\) を \(L\) から \(1\) まで順に試し、それぞれの \(k\) に対して文字列が一致するかどうかを判定する方法が考えられます。 しかし、文字列の比較には最悪で \(O(k)\) の時間がかかります。\(k\) を \(L\) から \(1\) までループさせると、全体で \(O(L^2)\) の計算量になります。 本問題の制約は \(L, M \le 5 \times 10^5\) であるため、最悪の場合に \(2.5 \times 10^{11}\) 回程度の計算が必要となり、実行時間制限に間に合わず TLE（Time Limit Exceeded） となってしまいます。

高速化のアイデア

「ある文字列の先頭（接頭辞）と、特定の位置から始まる部分文字列がどれだけ一致しているか」を高速に求める必要があります。 このような文字列のパターンマッチング問題を解くために、Z-algorithm（または KMP法、ローリングハッシュなど）が非常に有効です。

Z-algorithm を用いると、長さ \(N\) の文字列に対して、各位置から始まる部分文字列と全体の接頭辞との最長共通接頭辞（LCP: Longest Common Prefix）の長さを、全体で \(O(N)\) の時間計算量で求めることができます。

アルゴリズム

1. 左側接合（\(S\) の末尾 \(k\) 文字と \(T\) の先頭 \(k\) 文字の一致）

\(T\) の先頭と \(S\) の末尾を比較したいため、文字列 \(U = T + S\)（\(T\) の後ろに \(S\) を連結した文字列）を作成します。\(U\) の長さは \(M + L\) です。

この文字列 \(U\) に対して Z-algorithm を適用し、得られた配列を Z_U とします。 \(S\) の末尾 \(k\) 文字（\(1 \le k \le L\)）は、連結した文字列 \(U\) において、インデックス \(M + L - k\) から始まる部分文字列に対応します。 \(j = L - k\)（\(0 \le j < L\)）とおくと、開始位置は \(M + j\)、求める重なり幅は \(k = L - j\) と表せます。

Z_U[M + j] は、インデックス \(M + j\) から始まる部分文字列と \(U\)（すなわち \(T\)）の先頭との共通接頭辞の長さを表します。 したがって、Z_U[M + j] >= L - j が成り立てば、長さ \(L - j\) の重なりが存在することになります。 \(j\) を \(0\) から順に（重なり幅 \(k = L - j\) が大きい順に）探索し、条件を満たす最初の \(L - j\) が左側接合での最大重なり幅 ans_left となります。

2. 右側接合（\(T\) の末尾 \(k\) 文字と \(S\) の先頭 \(k\) 文字の一致）

同様に、\(S\) の先頭と \(T\) の末尾を比較したいため、文字列 \(V = S + T\)（\(S\) の後ろに \(T\) を連結した文字列）を作成します。\(V\) の長さは \(L + M\) です。

この文字列 \(V\) に対して Z-algorithm を適用し、得られた配列を Z_V とします。 \(T\) の末尾 \(k\) 文字（\(1 \le k \le L\)）は、連結した文字列 \(V\) において、インデックス \(L + M - k\) から始まる部分文字列に対応します。 \(j = M - k\) とおくと、\(k\) が \(L\) から \(1\) まで動くとき、\(j\) は \(M - L\) から \(M - 1\) まで動きます。 開始位置は \(L + j\)、求める重なり幅は \(k = M - j\) と表せます。

Z_V[L + j] が \(V\)（すなわち \(S\)）の先頭とどれだけ一致しているかを表すため、Z_V[L + j] >= M - j が成り立てば、長さ \(M - j\) の重なりが存在します。 \(j\) を \(M - L\) から順に（重なり幅 \(k = M - j\) が大きい順に）探索し、条件を満たす最初の \(M - j\) が右側接合での最大重なり幅 ans_right となります。

最後に、ans_left と ans_right のうち大きい方を出力します。

計算量

• 時間計算量: \(O(L + M)\) 文字列 \(U, V\) の長さはともに \(L + M\) です。Z-algorithm による配列の構築は線形時間 \(O(L + M)\) で行えます。その後の探索ループも最大で \(L\) 回のループであるため \(O(L)\) です。したがって、全体の時間計算量は \(O(L + M)\) となり、実行時間制限に対して非常に高速に動作します。

• 空間計算量: \(O(L + M)\) 連結した文字列 \(U, V\) および Z-algorithm の結果を格納する配列 Z_U, Z_V を保持するために、文字列の長さに比例したメモリを使用します。

実装のポイント

• AC-Library の活用: C++ では AtCoder Library (ACL) に atcoder::z_algorithm が用意されているため、これを利用することで自作する手間を省き、バグのない安全な実装が可能です。

• インデックスの計算: 連結した文字列における元の文字列の開始位置や、残り文字数のインデックス計算で \(1\) ずれる（オフバイワンエラー）が起きやすいため、紙に具体例を書き出すなどして慎重に設計することが重要です。

  • 左側接合：\(S\) の \(j\) 文字目（\(0\)-indexed）は、連結文字列 \(U = T + S\) の \(M + j\) 文字目に対応し、末尾までの長さは \(L - j\)。

  • 右側接合：\(T\) の \(j\) 文字目（\(0\)-indexed）は、連結文字列 \(V = S + T\) の \(L + j\) 文字目に対応し、末尾までの長さは \(M - j\)。

    ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L, M;
    if (!(cin >> L >> M)) return 0;

    string S, T;
    cin >> S >> T;

    // 左側接合: S の末尾 k 文字 と T の先頭 k 文字が一致
    string U = T + S;
    auto Z_U = atcoder::z_algorithm(U);
    int ans_left = 0;
    for (int j = 0; j < L; ++j) {
        if (Z_U[M + j] >= L - j) {
            ans_left = L - j;
            break;
        }
    }

    // 右側接合: T の末尾 k 文字 と S の先頭 k 文字が一致
    string V = S + T;
    auto Z_V = atcoder::z_algorithm(V);
    int ans_right = 0;
    for (int j = M - L; j < M; ++j) {
        if (Z_V[L + j] >= M - j) {
            ans_right = M - j;
            break;
        }
    }

    cout << max(ans_left, ans_right) << "\n";

    return 0;
}

---

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