Overview

This problem asks, given two DNA sequences (strings) \(S\) and \(T\), to find the maximum number of characters that can match (overlap) between the end of one string and the beginning of the other. We compute the maximum overlap width for two patterns: “left junction” where \(S\) is on the left and \(T\) is on the right, and “right junction” where \(T\) is on the left and \(S\) is on the right, then output the larger of the two.

Analysis

Naive Approach and Its Limitations

The simplest method is to try overlap widths \(k\) from \(L\) down to \(1\) in order. For example, in the case of left junction, we check whether the last \(k\) characters of \(S\) match the first \(k\) characters of \(T\). However, this method takes \(O(k)\) for each match check, resulting in \(O(L^2)\) total time. Given the constraints of this problem, \(L, M \le 5 \times 10^5\), the worst case would require approximately \(2.5 \times 10^{11}\) computations, which would exceed the time limit (TLE). Therefore, a more efficient \(O(L + M)\) algorithm is needed.

Application of KMP (LPS Array)

To efficiently find the longest length where a “prefix (beginning part)” and “suffix (ending part)” of a string match, we can use the LPS (Longest Prefix Suffix) array construction algorithm from the KMP (Knuth-Morris-Pratt) Algorithm.

The LPS array records, for each position in a string, “the length of the longest substring that is both a prefix and a suffix (excluding the string itself)”. The LPS array for a string of length \(N\) can be constructed in \(O(N)\) linear time.

We apply this property cleverly to our problem.

1. Left junction (overlapping the end of \(S\) with the beginning of \(T\)) Since we want to find the match between the beginning (prefix) of \(T\) and the end (suffix) of \(S\), we create a concatenated string \(P_1 = T + \text{"\#"} + S\) with a special separator character # in between. When we construct the LPS array for \(P_1\), the value of the last element represents “the longest match length that is both a prefix of \(P_1\) (starting from the beginning of \(T\)) and a suffix of \(P_1\) (ending at the end of \(S\))”, which gives us the maximum overlap width for the left junction.

2. Right junction (overlapping the end of \(T\) with the beginning of \(S\)) Similarly, by creating the string \(P_2 = S + \text{"\#"} + T\) and constructing its LPS array, we can find the maximum overlap width for the right junction.

Algorithm

KMP LPS Array Construction

The LPS array lps for a string pattern is constructed as follows:

1. Initialize the lps array with 0.
2. Prepare two pointers: i (search position, starting from 1) and j (length of the matched prefix, starting from 0).
3. Move i to the right while repeating the following:
   • If pattern[i] and pattern[j] do not match, move j back to a shorter prefix that might still match (j = lps[j-1]). Repeat this until they match or j = 0.
   • If pattern[i] and pattern[j] match, advance j by 1.
   • Record the value of j in lps[i].

Concrete Example

Consider the left junction for \(S = \text{"101"}\), \(T = \text{"0110"}\). The concatenated string is \(P_1 = T + \text{"\#"} + S = \text{"0110\#101"}\).

The computation process of the LPS array for this string is as follows:

Index i	Character P_1[i]	Value of lps[i]	Explanation
0	0	0	First character
1	1	0	No match
2	1	0	No match
3	0	1	Prefix "0" matches suffix "0"
4	#	0	No match due to separator character
5	1	0	No match
6	0	1	Prefix "0" matches suffix "0"
7	1	2	Prefix "01" matches suffix "01"

The value of lps[7] at the end is 2, meaning the maximum overlap width is 2 (the last "01" of \(S\) matches the first "01" of \(T\)), computed in \(O(L+M)\).

Complexity

• Time Complexity: \(O(L + M)\) The LPS array construction for a string of length \(L + M + 1\) runs in linear time \(O(L + M)\), since the total number of times pointer i advances to the right and j moves back is bounded by at most twice the string length. Since we perform this twice (for left junction and right junction), the overall complexity is also \(O(L + M)\), which comfortably fits within the time limit.

• Space Complexity: \(O(L + M)\) Since we store the concatenated strings \(P_1, P_2\) and their corresponding LPS arrays of length \(L + M + 1\), the space complexity is \(O(L + M)\).

Implementation Notes

• Importance of the separator character "#" If we concatenate as \(T + S\) without a separator character, the overlap width could exceed the length \(L\) of \(S\) and match into the interior of \(T\) (for example, when \(S\) is a complete substring of \(T\)). By the problem’s definition, junctions are performed between the ends, so the overlap width must be at most \(L\) (the length of \(S\)). By inserting the character "#", which never appears in \(S\) or \(T\), between them, we prevent the LPS search from matching across "#", correctly detecting only “end-to-end overlaps (at most \(L\))”.

  Source Code

import sys

def solve():
    # 入力の高速読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    L = int(input_data[0])
    M = int(input_data[1])
    S = input_data[2]
    T = input_data[3]
    
    # KMP法を用いて、pattern の最長自明でない接頭辞かつ接尾辞の長さを求める
    def get_max_overlap(pattern):
        n = len(pattern)
        lps = [0] * n
        j = 0
        for i in range(1, n):
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            lps[i] = j
        return lps[-1]

    # 左側接合: S の末尾 k 文字 と T の先頭 k 文字の一致 (T + '#' + S)
    # 右側接合: T の末尾 k 文字 と S の先頭 k 文字の一致 (S + '#' + T)
    ans1 = get_max_overlap(T + '#' + S)
    ans2 = get_max_overlap(S + '#' + T)
    
    print(max(ans1, ans2))

if __name__ == '__main__':
    solve()

---

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