如何在朴素字符串匹配算法中实现*通配符匹配？

我已经在朴素字符串匹配算法中实现了匹配单个字符的?通配符，但在添加可匹配一个或多个字符的*通配符时遇到了困难。

当前实现代码 #

pat为字符模式列表，txt为字符列表：

def search(pat,txt):
        M = len(pat)
        N = len(txt)
        
        for i in range(N-M+1):
            j=0
            while(j<M):
                if pat[j]=="?":
                    j+=1
                    continue
                if (txt[i+j]!=pat[j]):
                    break
                j+=1
                
    
            if(j==M):
                print("Pattern found at index ",str(i))

txt=["A","A","B","A","A","A","C","A","A","D","A","A","B","A","A","A","B","C","A"]
pat=["A","A","?","C"]
search(pat,txt)
# Pattern found at index  3
# Pattern found at index  14

txt=["A","A","B","A","A","A","C","A","A","D","A","A","B","A","A","A","B","C","A"]
pat=["A","A","B","C"]
search(pat,txt)
# Pattern found at index  14

期望实现效果 #

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["d","o","g","*","b","o","t","h"]
search(pat,txt)
# Pattern found at index  5
# Corresponding to ["d","o","g","i","l","o","v","e","b","o","t","h"]

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["i","*"]
search(pat,txt)
# Pattern found at index  8
# Corresponding to ["i","l","o","v","e","b","o","t","h"]

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["*","i"]
search(pat,txt)
# Pattern found at index  0
# Corresponding to ["C","a","t","o","r","d","o","g","i"]

请问该如何实现？

朴素匹配的线性遍历逻辑没法直接处理*的任意长度匹配，得改用分治匹配+回溯的思路实现。下面是贴合你原有代码结构的修改方案，能覆盖所有示例场景：

def search(pat, txt):
    N = len(txt)
    M = len(pat)

    def is_match(start_i):
        i = start_i
        j = 0
        while i < N and j < M:
            # 处理?通配符：匹配单个任意字符
            if pat[j] == "?":
                i += 1
                j += 1
            # 处理*通配符：匹配任意长度字符，尝试后续模式匹配
            elif pat[j] == "*":
                j += 1
                # *在模式末尾，直接匹配成功
                if j == M:
                    return True
                # 从当前位置开始，找能匹配*之后剩余模式的位置
                while i < N:
                    if is_match_helper(i, j):
                        return True
                    i += 1
                return False
            # 普通字符匹配
            elif txt[i] == pat[j]:
                i += 1
                j += 1
            # 字符不匹配，直接退出
            else:
                break
        # 跳过模式末尾的连续*
        while j < M and pat[j] == "*":
            j += 1
        # 模式全部匹配完成则成功
        return j == M

    def is_match_helper(i, j):
        # 辅助函数：检查txt从i开始是否匹配pat从j开始的无*模式
        while i < N and j < M:
            if pat[j] == "?":
                i += 1
                j += 1
            elif pat[j] == "*":
                return False
            elif txt[i] == pat[j]:
                i += 1
                j += 1
            else:
                return False
        # 跳过末尾剩余的*
        while j < M and pat[j] == "*":
            j += 1
        return j == M

    # 遍历所有可能的起始位置，输出所有匹配结果
    for start_i in range(N + 1):
        if is_match(start_i):
            print(f"Pattern found at index  {start_i}")
            # 计算匹配的子序列范围
            end_i = N
            # 从后往前找匹配的结束位置
            i_back = N - 1
            j_back = M - 1
            while j_back >= 0 and i_back >= start_i:
                if pat[j_back] == "*":
                    break
                if pat[j_back] == "?" or pat[j_back] == txt[i_back]:
                    i_back -= 1
                    j_back -= 1
                else:
                    break
            # 根据*的位置确定结束索引
            if pat[j_back] == "*":
                end_i = i_back + 1 + len(pat[j_back+1:])
            else:
                end_i = start_i + M
            print(f"Corresponding to {txt[start_i:end_i]}")

# 测试示例
txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["d","o","g","*","b","o","t","h"]
search(pat,txt)

print("\n---\n")

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["i","*"]
search(pat,txt)

print("\n---\n")

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["*","i"]
search(pat,txt)

代码说明 #

1. is_match函数：针对每个起始位置start_i，检查txt子序列是否匹配模式。遇到*时，会尝试让*匹配0到多个字符，直到找到能匹配后续模式的位置。
2. is_match_helper函数：专门处理*之后的无通配符（或仅含?）模式匹配，确保后续字符能准确对应。
3. 遍历所有可能的起始索引，输出所有匹配结果，同时计算并打印对应的子序列，完全符合你给出的示例需求。

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