Merge Two Strings Using the Longest Edge Overlap

Merge two ASCII strings by combining an overlapping suffix of the first string with an equal prefix of the second. Try both possible concatenation orders and choose the order with the longer overlap.

Function Signature

merge_edge_overlap(str1: str, str2: str) -> str

Rules

For an order (a, b), find the greatest integer k from zero through min(len(a), len(b)) such that the last k characters of a equal the first k characters of b. Its merged result is a followed by b with its first k characters removed.

Compare the greatest overlap for (str1, str2) with that for (str2, str1). Use the larger overlap. If the overlap lengths are equal, use (str1, str2).

Only suffix-to-prefix overlap counts; a string appearing strictly inside another does not by itself permit removal. A zero-length overlap is always valid.

Output

Return the merged string for the selected order. For this exercise, empty inputs are allowed and use the same rules.

Constraints

• 0 <= len(str1), len(str2) <= 200000.
• Strings contain ASCII characters with code points 32 through 126, inclusive, including spaces and punctuation.
• Comparisons are case-sensitive.
• Target O(len(str1) + len(str2)) time; linear auxiliary storage is allowed.

Examples

Input: str1 = "1234yyabc", str2 = "abcxxxx1234"

Output: "abcxxxx1234yyabc"

The overlap in the first order is abc, while the reverse order overlaps on 1234.

Input: str1 = "ab", str2 = "ba"

Output: "aba"

Both overlap lengths are one, so the original order wins.

Input: str1 = "abc", str2 = "abc"

Output: "abc"

Input: str1 = "", str2 = "hi"

Output: "hi"