如何获取两个Strings中首次出现的公共substrings？

嘿，这个需求我之前也帮人捋过，刚好给你梳理几种实用的实现思路和代码，分不同场景给你参考～先跟你对齐下需求：咱们要找的是两个字符串里都存在、且在各自字符串中出现位置最早的公共子串对吧？一般大家默认要的是最长的那个首次出现的，我先按这个来，也会提下如果要找任意长度的情况怎么调整～

方法一：暴力匹配法（简单易上手，适合短字符串） #

这个方法属于入门级，思路特别直白——遍历第一个字符串的所有可能子串，按出现顺序检查是否在第二个字符串里，为了找最长的，咱们从最长的子串开始往下查，找到第一个符合条件的直接返回就行。

Python代码实现：

def first_common_substring(str1, str2):
    # 先把短的字符串放前面，减少遍历次数
    if len(str1) > len(str2):
        str1, str2 = str2, str1
    
    # 从最长的可能子串长度开始往下遍历
    for length in range(len(str1), 0, -1):
        # 逐个取出当前长度的子串
        for i in range(len(str1) - length + 1):
            substr = str1[i:i+length]
            # 检查这个子串是否在第二个字符串里
            if substr in str2:
                # 因为从最长开始找，第一个找到的就是最长的首次出现的公共子串
                return substr
    # 没有公共子串的话返回空串
    return ""

用法示例：

s1 = "hello world"
s2 = "worxxhello"
print(first_common_substring(s1, s2))  # 输出 "hello"

⚠️ 缺点：如果字符串很长，效率会很低，时间复杂度是O(n²*m)（n是短串长度，m是长串长度），适合小字符串场景。

方法二：滑动窗口法（效率更高，适合中等长度字符串） #

要是你的字符串长度中等，暴力法就有点慢了，这时候滑动窗口法更合适。思路是把其中一个字符串固定，另一个“滑”过去，每次检查重叠部分的公共子串，记录最早出现的最长匹配。

Python代码实现：

def first_common_substring_sliding(str1, str2):
    max_match_len = 0
    match_start_idx = 0

    # 遍历所有可能的重叠起始位置
    for i in range(len(str1)):
        for j in range(len(str2)):
            k = 0
            # 计算当前重叠部分的最长连续匹配长度
            while i + k < len(str1) and j + k < len(str2) and str1[i+k] == str2[j+k]:
                k += 1
            # 如果当前找到的匹配更长，就更新记录（因为是按顺序遍历，第一个更长的就是最早出现的）
            if k > max_match_len:
                max_match_len = k
                match_start_idx = i
    
    if max_match_len == 0:
        return ""
    # 返回str1中对应的子串（也可以从str2取，结果一样）
    return str1[match_start_idx:match_start_idx+max_match_len]

这个方法的时间复杂度是O(n*m)，比暴力法提升不少，大部分日常场景都够用。

方法三：后缀数组法（最优效率，适合超大字符串） #

要是你处理的是百万级字符的超大字符串，上面俩方法就扛不住了，这时候得用后缀数组的思路——把两个字符串用一个特殊分隔符（比如#，注意这个字符不能在两个原字符串里出现）拼接起来，生成所有后缀后排序，找相邻后缀中跨分隔符的最长公共前缀，就是咱们要的最长公共子串，再确认下出现位置是不是最早的就行。

Python简化版实现：

def first_common_substring_suffix(str1, str2):
    separator = '#'
    # 拼接两个字符串，用分隔符区分开
    combined_str = str1 + separator + str2
    # 生成所有后缀
    suffixes = [combined_str[i:] for i in range(len(combined_str))]
    # 排序后缀，这样有公共前缀的后缀会挨在一起
    suffixes.sort()

    max_match_len = 0
    result_substr = ""

    # 遍历排序后的后缀，找跨分隔符的最长公共前缀
    for i in range(len(suffixes)-1):
        s_a = suffixes[i]
        s_b = suffixes[i+1]
        # 检查两个后缀是不是分别来自原两个字符串
        has_sep_a = separator in s_a
        has_sep_b = separator in s_b
        if has_sep_a != has_sep_b:
            k = 0
            # 计算公共前缀长度
            while k < len(s_a) and k < len(s_b) and s_a[k] == s_b[k]:
                k += 1
            # 更新最长匹配
            if k > max_match_len:
                max_match_len = k
                result_substr = s_a[:k]
    
    if not result_substr:
        return ""
    # 确认这个子串在原字符串中的首次出现位置，确保是最早的
    idx_in_str1 = str1.index(result_substr)
    idx_in_str2 = str2.index(result_substr)
    # 如果有多个同长度的子串，这里可以根据需求调整，比如选在str1中出现最早的
    return result_substr

这个方法的时间复杂度主要在排序后缀，是O((n+m)log(n+m))，处理超大字符串特别高效。

额外注意点 #

• 如果你的需求是任意长度的第一个出现的公共子串（比如只要找到第一个相同的字符就行），那可以把暴力法里的遍历顺序反过来，从长度1开始，找到第一个存在的子串就返回。
• 大小写敏感问题：如果需要忽略大小写，先把两个字符串都转成小写（或大写）再处理。
• 空字符串处理：提前判断如果其中一个字符串是空的，直接返回空串就行。

内容的提问来源于stack exchange，提问作者MaeLstroms Stroms