字符串匹配常用算法

1 暴力匹配

思想：逐一匹配

时间复杂度：

实现：

# -----------------------------------------
# https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/?ref=lbp
 
def find_brute_force(pat, txt):
    """在txt中找到pat的匹配项，并返回txt匹配时第一个索引"""
    m, n = len(pat), len(txt)
    for begin in range(n - m + 1):
        match = 0
        while match < m:
            if txt[begin + match] != pat[match]:
                break
            match += 1
        if match == m:
            print("Pattern found at index ", begin)
 
 
txt = "AABAACAADAABAAABAA"
pat = "AABA"
find_brute_force(pat, txt)

优化匹配：