查找两个字符之间的公共子字符串

查找两个字符序列之间的公共子字符串是指在两个给定字符串中找到相同的连续字符片段。这个过程可以用于比较文本相似度、数据校验等场景。通常，我们使用动态规划的方法来解决这个问题，例如著名的KMP算法（Knuth-Morris-Pratt 算法）或Boyer-Moore 搜索算法。

KMP算法通过构建一个部分匹配表（也称为失配函数），帮助我们在搜索过程中跳过无效的匹配尝试，减少了不必要的比较次数。Boyer-Moore算法则利用了坏字符规则和好后缀规则，分别针对当前字符不匹配和整体偏移的情况来优化搜索。

在Python中，你可以这样实现：

def find_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)

    # 创建长度为n+1的前缀和后缀数组
    prefix_function = [0] * (n + 1)
    for i in range(2, n + 1):
        j = prefix_function[i - 1]
        while j > 0 and str1[j] != str2[i - 1]:
            j = prefix_function[j]
        if str1[j] == str2[i - 1]:
            j += 1
        prefix_function[i] = j

    max_len = 0
    end_index = 0
    for i in range(n + 1):
        if prefix_function[i] == m:
            if m > max_len:
                max_len = m
                end_index = i - m
    return str1[end_index:end_index + max_len]

str1 = "hello"
str2 = "worldhello"
print(find_common_substring(str1, str2))  # 输出: 'hello'