Overview

Two strings \(S\) (length \(L\)) and \(T\) (length \(M\)) are given. We need to consider two types of joining: “left joining” where the suffix of \(S\) overlaps with the prefix of \(T\), and “right joining” where the suffix of \(T\) overlaps with the prefix of \(S\). For each, we find the maximum overlap length, and output the larger of the two.

Analysis

Naive Approach (Brute-force comparison)

One approach is to try overlap lengths \(k\) from \(L\) down to \(1\), and for each \(k\), check whether the strings match. However, comparing strings takes \(O(k)\) time in the worst case. Looping \(k\) from \(L\) down to \(1\) results in an overall time complexity of \(O(L^2)\). Given the constraints of this problem, \(L, M \le 5 \times 10^5\), the worst case would require approximately \(2.5 \times 10^{11}\) operations, which exceeds the time limit and results in TLE (Time Limit Exceeded).

Optimization Idea

We need to efficiently determine “how much the prefix of a string matches a substring starting at a specific position.” To solve such string pattern matching problems, Z-algorithm (or KMP algorithm, rolling hash, etc.) is extremely effective.

Using the Z-algorithm, for a string of length \(N\), we can compute the length of the longest common prefix (LCP) between the entire string’s prefix and the substring starting at each position, all in \(O(N)\) total time complexity.

Algorithm

1. Left Joining (matching the last \(k\) characters of \(S\) with the first \(k\) characters of \(T\))

Since we want to compare the prefix of \(T\) with the suffix of \(S\), we create the string \(U = T + S\) (concatenating \(S\) after \(T\)). The length of \(U\) is \(M + L\).

We apply the Z-algorithm to this string \(U\), and let the resulting array be Z_U. The last \(k\) characters of \(S\) (\(1 \le k \le L\)) correspond to the substring starting at index \(M + L - k\) in the concatenated string \(U\). Setting \(j = L - k\) (\(0 \le j < L\)), the starting position is \(M + j\), and the desired overlap length can be expressed as \(k = L - j\).

Z_U[M + j] represents the length of the common prefix between the substring starting at index \(M + j\) and the prefix of \(U\) (which is \(T\)). Therefore, if Z_U[M + j] >= L - j holds, an overlap of length \(L - j\) exists. We search \(j\) from \(0\) onwards (in decreasing order of overlap \(k = L - j\)), and the first \(L - j\) satisfying the condition is the maximum overlap for left joining, ans_left.

2. Right Joining (matching the last \(k\) characters of \(T\) with the first \(k\) characters of \(S\))

Similarly, since we want to compare the prefix of \(S\) with the suffix of \(T\), we create the string \(V = S + T\) (concatenating \(T\) after \(S\)). The length of \(V\) is \(L + M\).

We apply the Z-algorithm to this string \(V\), and let the resulting array be Z_V. The last \(k\) characters of \(T\) (\(1 \le k \le L\)) correspond to the substring starting at index \(L + M - k\) in the concatenated string \(V\). Setting \(j = M - k\), as \(k\) ranges from \(L\) to \(1\), \(j\) ranges from \(M - L\) to \(M - 1\). The starting position is \(L + j\), and the desired overlap length can be expressed as \(k = M - j\).

Since Z_V[L + j] represents how much the substring matches the prefix of \(V\) (which is \(S\)), if Z_V[L + j] >= M - j holds, an overlap of length \(M - j\) exists. We search \(j\) from \(M - L\) onwards (in decreasing order of overlap \(k = M - j\)), and the first \(M - j\) satisfying the condition is the maximum overlap for right joining, ans_right.

Finally, output the larger of ans_left and ans_right.

Complexity

• Time Complexity: \(O(L + M)\) The lengths of strings \(U, V\) are both \(L + M\). Constructing the array with the Z-algorithm can be done in linear time \(O(L + M)\). The subsequent search loop runs at most \(L\) iterations, so it is \(O(L)\). Therefore, the overall time complexity is \(O(L + M)\), which runs very efficiently within the time limit.

• Space Complexity: \(O(L + M)\) Memory proportional to the string length is used to store the concatenated strings \(U, V\) and the arrays Z_U, Z_V holding the Z-algorithm results.

Implementation Notes

• Using AC-Library: In C++, AtCoder Library (ACL) provides atcoder::z_algorithm, which can be used to avoid the effort of implementing it yourself and ensures a bug-free, safe implementation.

• Index Calculation: Off-by-one errors are easy to make when calculating the starting positions of original strings within the concatenated string and the remaining character counts. It is important to carefully design this by writing out concrete examples on paper.

  • Left joining: The \(j\)-th character of \(S\) (\(0\)-indexed) corresponds to the \((M + j)\)-th character of the concatenated string \(U = T + S\), and the length from that position to the end is \(L - j\).

  • Right joining: The \(j\)-th character of \(T\) (\(0\)-indexed) corresponds to the \((L + j)\)-th character of the concatenated string \(V = S + T\), and the length from that position to the end is \(M - j\).

    Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.