如何使用Python实现Brute force pattern暴力字符串匹配算法并验证测试用例

算法说明 #

暴力字符串匹配（Brute Force Pattern）的核心逻辑是：遍历文本串所有可能的起始位置，逐一比对该位置开始的子串与模式串是否完全一致，直到找到匹配项或遍历完所有可行位置。最坏时间复杂度为O(nm)*，其中n为文本串长度，m为模式串长度。

代码实现 #

def brute_force_match(text: str, pattern: str) -> int:
    n = len(text)
    m = len(pattern)
    # 边界处理：模式串长度大于文本串，不可能匹配
    if m > n:
        return -1
    # 边界处理：空模式串默认匹配起始位置0
    if m == 0:
        return 0
    # 遍历所有可行的起始位置，最大起始位置为n-m
    for i in range(n - m + 1):
        j = 0
        # 逐字符比对子串和模式串
        while j < m and text[i + j] == pattern[j]:
            j += 1
        # 全部字符匹配成功，返回起始索引
        if j == m:
            return i
    # 遍历完成无匹配项
    return -1

# 测试用例执行
if __name__ == "__main__":
    # Test case 1
    text1 = "10110100110010111"
    pattern1 = "001011"
    res1 = brute_force_match(text1, pattern1)
    print(f"Test case#1 匹配结果：起始索引为{res1}" if res1 != -1 else "Test case#1 无匹配结果")
    # Test case 2
    text2 = "It is never too late to have a happy childhood"
    pattern2 = "happier"
    res2 = brute_force_match(text2, pattern2)
    print(f"Test case#2 匹配结果：起始索引为{res2}" if res2 != -1 else "Test case#2 无匹配结果")
    # Test case 3
    text3 = "NOBODY_NOTICED_HIM"
    pattern3 = "NOT"
    res3 = brute_force_match(text3, pattern3)
    print(f"Test case#3 匹配结果：起始索引为{res3}" if res3 != -1 else "Test case#3 无匹配结果")

运行输出 #

Test case#1 匹配结果：起始索引为6
Test case#2 无匹配结果
Test case#3 匹配结果：起始索引为7

结果验证 #

• 测试用例1：模式串001011在文本串索引为6的位置匹配成功，符合预期
• 测试用例2：文本串仅存在happy子串，无happier，返回无匹配符合预期
• 测试用例3：模式串NOT在文本串索引为7的位置匹配成功，符合预期

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