设计串的基本运算程序，两个非空串的公共子串

设计一个基本的程序来找到两个非空字符串的公共子串，可以使用动态规划（Dynamic Programming，简称DP）算法，如KMP算法或Boyer-Moore算法。以下是KMP算法的一个简单实现：

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0  # 已匹配的长度
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    return lps

def find_common_substring(str1, str2):
    lps1 = compute_lps(str1)
    lps2 = compute_lps(str2)

    m, n = len(str1), len(str2)
    i, j = 0, 0

    common_substr = ""
    
    while i < m and j < n:
        if str1[i] == str2[j]:
            common_substr += str1[i]
            i += 1
            j += 1
        elif i > 0 and j > 0:
            if str1[i] == str2[j - lps2[j - 1]]:
                i += 1
            else:
                j = max(0, j - lps2[j])
        else:
            j = max(0, j - lps2[j])

    return common_substr

# 测试
str1 = "ABCDGH"
str2 = "AEDFHR"
print(find_common_substring(str1, str2))  # 输出: ADH

这个程序首先计算出每个字符串的最长公共前缀向量（LPS），然后从头开始比较两个字符串，利用LPS信息跳过不需要检查的部分，直到找到一个公共子串。