在经典的模式匹配问题中，我们给出了长度为n的文本字符串T和长度为m的模式字符P，并希望明确是否P是T的一个字串。如果是，则希望找到P在T中开始位置的最低索引j，比如T[j:j+m]和P匹配，或者从T中找到所有的P的开始位置索引。

在本文中，我们介绍三种匹配算法，难度依次递增。

1.暴力穷举法

穷举法是极其常用的一种算法，不止在匹配算法上，还在优化某些功能上也有涉及。

穷举法即为列举出所有的可能情况，并加以逐一判断。

def find_brute(T, P):
    """Return the lowest index of T at which substring P begins (or else -1)"""
    n, m = len(T), len(P)   # Get length of T and P's
    for i in range(n-m+1):  # Because it can't be P after T[n-m+1:]
        k = 0               # Record the index of P
        while k < m and T[i + k] == P[k]:   # The match was incomplete and successful
            k += 1
        if k == m:          # Match successful
            return i
    return -1

这是一个简单的暴力枚举的匹配算法，判断P是否是T的一个子串，是则返回第一次出现的索引，否则返回-1，算法优化在不改变代码结构的基础上，就是这里扣一点，那里扣一点。例如range函数的范围我们给出了n-m+1，因此对于P长度越大，则性能优化最大。

我们可以看到外层for循环至多执行了n-m+1次，内存while循环至多执行了m次，因此，该算法在最坏的情况下的运行时间是

测试一下：

T = "abcafgasdfwefacasdfe"
P = "asd"
print(find_brute(T, P))

运行结果：

2.Boyer-Moore算法

Boyer-Moore算法的主要思想是通过增加两个可能省时的启发式算法来提升穷举法的运行时间：

1.镜像启发式（Looking-glass )：当测试P相对于T可能的位置时，可以从P的尾部开始比较，然后从后向前移动直到P的头部。

2.字幕跳跃启发式(-jump )：在测试P在T中可能的位置时，有着相应模式字符P[k]的文本字符T[i] = c的不匹配情况按如下方法处理：如果P中任何位置都不包含c，则将P完全移动到T[i]之后，(因为它不能匹配P中任何一个字符）；否则，直到P中出现字符c并与T[i]一致才移动P。

def find_boyer_moore(T, P):
    """Return the lowest index of T at which substring P begins (or else -1)"""
    n, m = len(T), len(P)   # get length of T and P's
    if m == 0: return 0     # Return 0 if m's length is 0
    last = {}               # Create a dictionary for P
    for k in range(m):      # Add each character position of P to the dictionary
        last[P[k]] = k
        # align end of pattern at index m-1 of text
    i = m-1                 # This is a pointer to T
    k = m-1                 # This is a pointer to P
    while i < n:            # Use the while loop to iterate over T
        if T[i] == P[k]:    # If the match is successful and all matches
            if k == 0:
                return i

            else:           # If the match is successful but no all matches
                i -= 1      # Pointer forward
                k -= 1
        else:
            j = last.get(T[i], -1)
            # If the current character appears in the mode character,Return index ,else -1
            i += m - min(k, j+1)
            # Returns the starting pointer position by adding up the number of matched characters
            k = m-1
            # Restore k
    return -1

这段代码的一个核心在于以下三条：

j = last.get(T[i], -1)
i += m - min(k, j+1)
k = m-1

通过字典last.get返回值判断是否匹配成功过，如果字符在P中出现过，则返回索引（即还有多少个字符没有匹配，然后通过m减去得到已经匹配的数量，在累加到i上，即可使i指针回到最初的位置，正常向后推进），否则返回-1，而在第二行中，使用了min函数判断k和j+1的大小（如果没有匹配到，则j+1得到0，m-0就会使指针i直接向后推进m个位置，极大程度上减少了运行速度。如果匹配成功过，则也可以通过min函数判断k和j+1的大小使得m-min(k, j+1)能取得最大值）。
最后呢，将k还原为最开始的m-1.
如果使用传统的查找表，在最坏的情况下BM算法的运行时间是o(nm)
测试一下

print(find_boyer_moore("abedef", "ede"))

运行结果：

3.Knuth-Morris-Pratt算法

KMP算法对于模式有一个确定的调整，如果发现一些匹配的字符但后来又发现不匹配，在模式下一次重新匹配时，我们忽略所有由成功的比较而获得的信息。这样避免了信息的浪费，并且它能达到的运行时间为

, 这是渐近最优运行时间。即在最坏的情况下，任何模式匹配算法将会对文本的所有字符和模式的所有字符检查至少一次。KMP算法的主要思想是预先计算模式部分之间的自重叠，从而当不匹配发生在一个位置时，我们在继续搜寻之前就能立刻知道移动模式的最大数目。

失败函数

为了实现KMP算法，我们需要预先计算失败函数

，该函数用于表示匹配失败时P对应的位移。具体地，失败函数f(k)定义为P的最长前缀的长度，它是P[1:K+1]的后缀（这里没有包含P[0]，因为至少会移动一个单元）。如果在字符P[k+1]中找不到匹配，函数f(k)会告诉我们多少紧接着的字符可以用来重启模式

def compute_kmp_fail(P):
    """Utility that computes and returns KMP 'fail' list."""
    m = len(P)
    fail = [0] * m          # by default. presume overlap of 0 everywhere
    j = 1
    k = 0

    while j < m:            # compute f(j) during this pass, if nonzero
        if P[j] == P[k]:    # k + 1 characters match thus fat
            fail[j] = k + 1
            j += 1
            k += 1
        elif k > 0:         # k follows a matching prefix
            k = fail[k-1]
        else:               # no match found starting at j
            j += 1
    return fail

这是一个失败函数，通过双指针来匹配最大的重复前缀，它将模式与KMP中的模式进行比较。每次有两个匹配的字符，我们设置f(j0 = k + 1。因为在整个算法中已经有j > k，当使用它时，f(k - 1)总是被定义好的。

def find_kmp(T, P):
    """Return the lowest index of T at which substring P begins (or else -1)"""
    n, m = len(T), len(P)           # Get length of T and P's
    if m == 0: return 0             # Return 0 if P's length is 0
    fail = compute_kmp_fail(P)      # Call the compute_kmp_fail function to get the return list
    j = 0
    k = 0
    while j < n:
        if T[j] == P[k]:
            if k == m - 1:          # Complete match
                return j - m + 1    # Return the index of the first matched character
            j += 1                  # Match successful but no all, pointer forward
            k += 1
        elif k > 0:                 # Match failure but succeeded
            k = fail[k - 1]         # Prefix rebound
        else:
            j += 1
    return -1

这是一个KMP算法的实现，其中 k = fail[k-1]实现了不完全匹配时触发的前缀回跳，以此来减少匹配次数，实现算法优化。不太理解的可以打个断点观察一下k的变化。

测试一下：

print(find_kmp("ababababef", "ababef"))

运行结果：