Overview

Given two strings \(S\) and \(T\), the problem asks to find the larger of: the longest match between a suffix of \(S\) and a prefix of \(T\) (left join), and the longest match between a suffix of \(T\) and a prefix of \(S\) (right join). We solve this efficiently using the Z-function.

Analysis

Problem Reformulation

• Left join: Find the maximum \(k\) such that the last \(k\) characters of \(S\) = the first \(k\) characters of \(T\)
• Right join: Find the maximum \(k\) (with \(k \le L\)) such that the last \(k\) characters of \(T\) = the first \(k\) characters of \(S\)

Issues with a Naive Approach

If we naively compare strings for each \(k\), a single comparison takes \(O(k)\), and the total becomes \(O(L^2)\), which results in TLE when \(L\) is up to \(5 \times 10^5\).

Solution

By using the Z-function, we can compute the “longest match length with the prefix” for each position in a string in \(O(N)\) time. We combine this with the string concatenation technique.

Algorithm

What is the Z-function?

For a string \(s\), the Z-function computes an array where \(z[i]\) = “the length of the longest common prefix between \(s[i:]\) and \(s[0:]\)” for all \(i\). It can be computed in linear time.

Computing the Left Join

We want to find the maximum \(k\) satisfying \(S[L-k:L] = T[0:k]\).

Construct the concatenated string \(T + \\) + S\( and compute the Z-function. The Z-value at position \)M+1+j\( (corresponding to the \)j\(-th character of \)S\() represents "the longest common prefix length between the beginning of \)T\( and \)S[j:]$“.

If the entirety of \(S[j:]\) (of length \(L-j\)) matches the beginning of \(T\), i.e., \(z[M+1+j] \ge L-j\), then joining with overlap width \(k = L-j\) is possible. By searching \(j\) from \(0\) onwards, the first match found gives the maximum \(k\).

Computing the Right Join

We want to find the maximum \(k\) (with \(k \le L\)) satisfying \(T[M-k:M] = S[0:k]\).

Construct the concatenated string \(S + \\) + T\( and compute the Z-function. The Z-value at position \)L+1+j\( (corresponding to the \)j\(-th character of \)T\() represents "the longest common prefix length between the beginning of \)S\( and \)T[j:]$”.

If the entirety of \(T[j:]\) (of length \(M-j\)) matches the beginning of \(S\), i.e., \(z[L+1+j] \ge M-j\), then joining with overlap width \(k = M-j\) is possible. Due to the constraint \(k \le L\), we set \(j \ge M-L\) and search \(j\) starting from \(M-L\).

Concrete Example

When \(S = \) 101, \(T = \) 01001:

• Left join: Search for a match between the end of \(S\) and the beginning of \(T\) → the suffix 01 of 101 = the prefix 01 of 01001 → \(k=2\)
• Right join: Search for a match between the end of \(T\) and the beginning of \(S\) → the suffix 1 of 01001 = the prefix 1 of 101 → \(k=1\)

The answer is \(\max(2, 1) = 2\).

Complexity

• Time complexity: \(O(L + M)\) (Z-function computation is linear, and the search is also linear)
• Space complexity: \(O(L + M)\) (for storing the concatenated string and the Z-array)

Implementation Notes

• By inserting a separator $ (a character not contained in the original strings) in the concatenated string, we prevent Z-values from matching across the boundary.

• For the left join, by searching \(j\) from the smallest value, the maximum \(k = L - j\) is obtained at the first position satisfying the condition, allowing an immediate break.

• For the right join, pay attention to the constraint \(k \le L\), and set the search starting position to \(j = \max(0, M-L)\).

  Source Code

import sys

def z_function(s):
    n = len(s)
    if n == 0:
        return []
    z = [0] * n
    z[0] = n
    l, r = 0, 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    L = int(tokens[0])
    M = int(tokens[1])
    S = tokens[2]
    T = tokens[3]
    
    ans = 0
    
    # Left junction: S then T
    # We need suffix of S of length k == prefix of T of length k, for max k (1 <= k <= L)
    # Build string: T + '#' + S, then use Z-function
    # We look at positions corresponding to S part, specifically the last L characters
    # For position i in the concatenated string corresponding to S[j], 
    # if z[i] >= (len(S) - j) where j is position in S... 
    # Actually, let's think differently.
    # We want: S[L-k:L] == T[0:k]
    # Concatenate: T + '$' + S
    # z[i] at position (M+1+j) for j in [0, L-1] gives the length of match between T[0:...] and S[j:...]
    # We need S[j:L] == T[0:L-j], i.e., z[M+1+j] >= L - j
    # And k = L - j, so we want to maximize k = L - j such that z[M+1+j] >= L - j
    
    concat1 = T + '$' + S
    z1 = z_function(concat1)
    
    for j in range(L):
        k = L - j  # overlap width
        idx = M + 1 + j  # position in concatenated string
        if z1[idx] >= k:
            ans = max(ans, k)
            break  # since we iterate j from 0, first match gives maximum k
    
    # Right junction: T then S
    # We need suffix of T of length k == prefix of S of length k, for max k (1 <= k <= L)
    # Concatenate: S + '$' + T
    # z[i] at position (L+1+j) for j in [0, M-1] gives match length between S[0:...] and T[j:...]
    # We need T[j:j+k] == S[0:k] where k = M - j... no wait.
    # We need T[M-k:M] == S[0:k], so j = M - k, and we need z[L+1+j] >= k = M - j
    # But k <= L, so j >= M - L
    # We want to maximize k, so minimize j. j starts from max(0, M-L).
    
    concat2 = S + '$' + T
    z2 = z_function(concat2)
    
    start_j = M - L  # since k = M - j <= L means j >= M - L
    if start_j < 0:
        start_j = 0
    
    for j in range(start_j, M):
        k = M - j  # overlap width
        if k <= 0:
            break
        idx = L + 1 + j
        if z2[idx] >= k:
            ans = max(ans, k)
            break  # first match gives maximum k since j increasing means k decreasing
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.