Merge Suffix Prefix

Overview

The goal is to join two strings, str1 and str2, by finding the longest overlap where the end of the first string matches the beginning of the second. If an overlap exists, we merge those matching parts into one. If no overlap exists, we simply concatenate them.

The key observation is that the maximum possible length of this overlap is the length of the shorter string. We are looking for the largest $k$ such that str1[-k:] == str2[:k].

Brute Force

In a brute-force approach, we check every possible overlap length $k$, starting from the maximum possible length (the size of the smaller string) down to 1. As soon as we find a match, we know it is the longest suffix-prefix overlap.

If we iterate through all lengths and find no match, the overlap length is 0.

def merge_suffix_prefix(str1: str, str2: str) -> str:
    n1 = len(str1)
    n2 = len(str2)
    
    # The maximum possible overlap is the length of the shorter string
    max_possible_overlap = min(n1, n2)
    
    # Check lengths from longest to shortest
    for length in range(max_possible_overlap, 0, -1):
        # Suffix of str1 of size 'length'
        suffix = str1[n1 - length:]
        # Prefix of str2 of size 'length'
        prefix = str2[:length]
        
        if suffix == prefix:
            # Found the longest overlap, return merged result
            return str1 + str2[length:]
            
    # No overlap found
    return str1 + str2

Time complexity: O(N^2) — We iterate up to N times (where N is the length of the strings), and in each iteration, we perform a string comparison that can take O(N) time. Space complexity: O(N) — Slicing strings creates new string objects in memory before the comparison.

Optimal / Best Approach

The "optimal" way to handle string matching of suffixes and prefixes is typically via the KMP (Knuth-Morris-Pratt) preprocessing algorithm. Specifically, we can use the Partial Match Table (also known as the "pi table" or "failure function").

To find the overlap between str1 and str2, we can create a combined string: combined = str2 + "#" + str1

By computing the KMP failure function for this combined string, the value of the last element in the table will tell us the length of the longest proper prefix of the combined string that is also a suffix of the combined string. Because of the # separator, this value is guaranteed to represent the longest prefix of str2 that matches a suffix of str1.

def merge_suffix_prefix(str1: str, str2: str) -> str:
    if not str1 or not str2:
        return str1 + str2

    # Create a combined string for KMP: prefix_str + separator + suffix_str
    # We want the prefix of str2 to match the suffix of str1
    combined = str2 + "#" + str1
    n = len(combined)
    pi = [0] * n
    
    # Compute KMP failure function (Partial Match Table)
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = pi[j - 1]
        if combined[i] == combined[j]:
            j += 1
        pi[i] = j
    
    # The last value in pi table is the length of the longest overlap
    overlap_len = pi[-1]
    
    return str1 + str2[overlap_len:]

Time complexity: O(N + M) — Where N and M are the lengths of str1 and str2 respectively. Building the KMP table is linear relative to the length of the combined string. Space complexity: O(N + M) — We store the combined string and the pi table, both of which are proportional to the sum of the input lengths.

Edge Cases

• Empty Strings: If str1 or str2 is empty, the logic correctly returns the non-empty string.
• No Overlap: The overlap_len will result in 0, and the strings are concatenated normally.
• Full Overlap: If str1 is "abc" and str2 is "abc", the result is "abc" (length 3 overlap).
• String 1 is a prefix of String 2: (Example: "abc", "abcdef"). The overlap length will be 3, resulting in "abcdef".

Fast