Overview

When joining strings \(S\) and \(T\) by “overlapping at least one character,” we find the maximum overlap width \(k\) for both left-side joining (\(S\)→\(T\)) and right-side joining (\(T\)→\(S\)).

Analysis

What is required for joining is “matching at the ends.”

• Left-side joining: The last \(k\) characters of \(S\) = The first \(k\) characters of \(T\)
  → We need to check “how far each suffix of \(S\) matches a prefix of \(T\)”
• Right-side joining: The last \(k\) characters of \(T\) = The first \(k\) characters of \(S\)
  → We need to check “how far each suffix of \(T\) matches a prefix of \(S\)” (with the constraint \(k\le L\))

If we naively try all \(k=1..L\) and compare, each comparison takes \(O(L)\) in the worst case, resulting in \(O(L^2)\) overall, which is too slow for \(L\le 5\times 10^5\).

Therefore, we use the Z algorithm, which can efficiently compute “the longest common prefix (LCP) between a prefix of a string and a substring starting at another position” all at once, achieving \(O(L+M)\) overall.

Algorithm

1. What is the Z Algorithm?

For a string \(P\), we construct an array \(Z\) where: - \(Z[i]\) = the number of characters that match from the beginning between \(P[0:]\) (the start of the entire string) and \(P[i:]\)

This is computed for all \(i\) in \(O(|P|)\).

2. Left-side joining (suffix of \(S\) and prefix of \(T\))

We want the maximum \(k\) (\(1\le k\le L\)) such that: - \(S[L-k:] = T[:k]\)

To view this as “the match length between a prefix of \(T\) and each suffix of \(S\),” we construct: - \(P = T + \text{sep} + S\) (using '2' as a separator character that doesn’t appear in 0 or 1)

and compute the Z array.

The length of the suffix starting at position pos (\(0\le pos < L\)) in \(S\) is: - \(\text{need} = L - pos\)

The starting position of that suffix in \(P\) is i = (M+1) + pos, so: - If \(Z[i] \ge \text{need}\), then the first \(\text{need}\) characters of \(T\) match \(S[pos:]\)
→ Left-side joining with overlap width \(k=\text{need}\) is possible

We check all pos and take the maximum \(\text{need}\) as left_max.

3. Right-side joining (suffix of \(T\) and prefix of \(S\))

We want the maximum \(k\) (\(1\le k\le L\)) such that: - \(T[M-k:] = S[:k]\)

This time, we want to compare a prefix of \(S\) with each suffix of \(T\), so we construct: - \(P2 = S + \text{sep} + T\)

and compute the Z array.

The length of the suffix starting at position pos (\(0\le pos < M\)) in \(T\) is: - \(\text{need} = M - pos\)

The starting position of that suffix in \(P2\) is i = (L+1) + pos, so: - If \(Z2[i] \ge \text{need}\), then the first \(\text{need}\) characters of \(S\) match \(T[pos:]\)
→ Right-side joining with overlap width \(k=\text{need}\) is possible

However, since the condition requires \(k\le L\), we only need to look at suffixes with \(\text{need}\le L\).
This corresponds to pos >= M-L (suffixes of length at most \(L\)), so in the code: - We start scanning from start_pos = M - L.

Finally, max(left_max, right_max) is the answer, and if neither can achieve at least 1, we output 0.

Complexity

• Time complexity: \(O(L+M)\)
  (Running the Z algorithm twice on strings of length \(L+M+1\))
• Space complexity: \(O(L+M)\)
  (Concatenated strings and Z arrays)

Implementation Notes

• The separator character sep must be a character not contained in 0 or 1 (here we use '2'). This prevents false matches across the boundary between \(T\) and \(S\) (or \(S\) and \(T\)).

• For left-side joining, we exhaustively search “each suffix of \(S\) (of length \(L-pos\))” and it succeeds if z[i] >= need.

• For right-side joining, we only need to look at “suffixes of \(T\) with length \(\le L\),” so we set the starting pos to M-L to avoid unnecessary computation.

• Since “concatenation without overlap is prohibited,” if no \(k\ge 1\) exists, we output 0.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.