字符串内查找指定子串出现位置的算法优化方法

本文不赘述，而是基于对最后两篇大神参考文章的一些自我理解。大神的文章简单易懂，建议先吃。

文章目录

取得成果

实现的效果类似于字符串中的 find 方法

m='this is a great world'
m.find('great')
Out[43]: 10
m.find('nice')
Out[44]: -1

查找子字符串在 m 字符串中出现的位置，返回的最终下标是 10，即 g 出现的位置。如果未找到，则返回 -1。

蛮力匹配的缺点

为了表达方便，匹配的字符串称为主字符串，长度设置为m，指针为i，用于匹配的字符串称为子字符串，长度设置为n，指针为j。

要找到子字符串出现的位置，很容易想到一个蛮力匹配方法，从主字符串下标 0 开始，依次匹配子字符串的每个元素，如果不满足，则移动到下标 1，重复匹配。直到没有找到下标 m-n+1，才肯定找不到指示，然后重复匹配结束，所以最差的时间复杂度是 O（（m-n+1）*n）。

显然，这里的两个指针 i 和 j 一直在主弦和子弦上来回移动，消耗了大量时间，但这种来回移动是没有必要的。请

看下面的例子。

主字符串和子字符串是 ABAB。当第一次匹配时，i 移动到 c 的下标为 3，j 也移动到 b 的下标为 3，并且相应的元素不相等。根据蛮力匹配，i 将返回 1，j 将返回 0 并重新开始匹配。

但是我和J真的有必要回去吗？

我们先看主字符串的指针i，因为我们已经知道下标为1的元素b肯定与子字符串的第一个元素a不同，那么就没有必要再比较了，下标为2的元素a必须与子字符串的第一个元素a相同， 而且没有必要重复比较，所以我可以完全不变。子字符串的指针 j 相同，因为已经知道前一个字符 a 与第一个字符 a 相同，因此似乎直接返回下标 1 的元素并继续匹配就足够了。

所以一个简单的分析表明，i 根本不需要移动，只需将 j 从 3 移动到 1，然后使用 m[i] 和 n[j] 继续比较。

我们在这里只是进行情感分析，KMP算法实际上是用算法实现的。

KMP算法原理

最长的前缀

首先，对于字符串来说，有一个前缀和后缀的概念需要理解清楚。前缀是从第一个字符开始并以任何不结束字符结束的子字符串，例如 x、习、xia、xiao、xiaof，后缀是从最后一个字符开始并上升到不结束字符的子字符串，例如 u、fu、ofu、aofu、iaofu。

在一组前缀和后缀中相交的最长子字符串称为最长前缀。例如，字符串前缀为 a、ab、aba、abac、abaca，后缀为 、acaba、caba、aba、ba、a，交集仅为 aba，因此最长的前缀也是 aba

理解最长前缀是理解KMP算法的关键，因为无论i和j位于何处，对于已经成功匹配的部分，主字符串和子字符串的内容都是一样的。如果有最长的前缀，那么最长的前缀部分可以跳过而不重复匹配，并且 i 不需要更改（让 j 再往前走一点以达到相同的目的）j 不需要更改为 0。

用我自己的话来说，KMP算法的原理是主字符串的指针i永远不会回溯，子字符串的指针j会根据此时匹配内容的最长前缀进行适当的回溯。

例如，在下图中，当 i=4 和 j=4 不相等时，i 不变，子字符串 0 到 j-1 位置是前 4 个字符 abab，最长前缀为 2，下一个数字为 j=2。之后，从 j=2 和 i=4 继续比较，循环继续。

因此，如果你能知道子字符串每个位的回溯的新位置，那就非常简单了。在KMP中，有一个特殊的列表用来记录这个，它记录了每个回溯位置对应的列表称为字符串的下一个数组（有的称为失败数组，简而言之，就会有一个数组），next[j]是j位置不匹配时要追踪的下标。

代码实现

让我们先看一下如何获取下一个字符串数组，然后在已知下一个数组时迭代它要容易得多。

下一个数组部分

查找字符串的下一个数组实际上是一个匹配问题，但它等同于子字符串匹配本身。在这种情况下，从下标 1 开始遍历主字符串，从下标 0 开始逐个比较子字符串。当主字符串遍历时，如果匹配成功，则表示下标 i 位置最长的前缀是下标 j（长度 j+1），那么如果 i+1 位置没有匹配，则返回下标 j+1（长度 j+2）的位置继续匹配，因此分别将 1 加到 i 和 j，然后 next[i]=j 加入下一个数组。如果没有匹配成功，匹配将继续，将下一个数组找到子字符串的当前最长前缀。

最后，考虑特殊情况，如果下标为 1 的元素不匹配，则返回下标 0 并继续匹配。如果下标 0 不匹配，则认为规范为 -1，主字符串的指针被迫向前移动一位再进行比较。

这里特别需要注意的是，下标和长度之间有 1 个间隙

def getNext(p: str) -> list:
    """
    当str在list某个下标位置匹配失败时候，从list对应下标的值的位置开始重新匹配
    """
    next = [0] * (len(p))  # 不事先赋值后面不能用下标去修改
    next[0] = -1  # 人为规定
    i = 0
    j = -1
    while i < len(p) - 1:  # 因为会自加1所以注意临界条件
        if j == -1 or p[i] == p[j]:
            # 意味着在下标为i的地方，最长前缀的长度为j+1，所以如果是在第i+1位匹配失败，意味着最长前缀长度为j+2
            # 所以要继续从下标为j+1（也就是长度j+2）的地方开始继续查找
            i += 1
            j += 1
            next[i] = j
        else:
            # 从前面已经匹配的地方再次查找
            j = next[j]
    return next

这里聪明的是，当匹配失败时，因为 j 必须小于 i，所以下一个数组中一定已经有一个值 next[j]，可以用来查询然后返回并再次匹配。

字符串匹配部分

有了下一个数组，进行字符串匹配就容易多了。

def KMP(m: str, s: str) -> int:
    """
    在m中查找n第一次出现的下标
    :param m: 被匹配的长字符串
    :param s: 用来做模式匹配的短字符串
    :return: 返回匹配成功后的起始位置的下标
    """
    next = getNext(s)
    i = 0
    j = 0
    while i < len(m) and j < len(s):
        if j == -1 or m[i] == s[j]:
            i += 1
            j += 1
        else:
            j = next[j]
    if j == len(s):
        return i - j
    return -1

如果匹配成功，则 i 和 j 都加 1，如果没有匹配，则 j 将下一个数组查询回新位置并继续匹配。在最后两个结果中，如果子字符串遍历完成，则返回起始位置 i-j，否则找不到主字符串遍历，返回 -1。

因为有两个方便，遍历子字符串以查找下一个数组，以及遍历主字符串进行实际搜索，因此时间复杂度为 O（m+n）。

完整代码如下

#! /usr/bin/env python
# -*- coding: utf-8 -*- 
# @author: xiaofu
# @date: 2020-Sep-01
def getNext(p: str) -> list:
    """
    当str在list某个下标位置匹配失败时候，从list对应下标的值的位置开始重新匹配
    """
    next = [0] * (len(p))  # 不事先赋值后面不能用下标去修改
    next[0] = -1  # 人为规定
    i = 0
    j = -1
    while i < len(p) - 1:  # 因为会自加1所以注意临界条件
        if j == -1 or p[i] == p[j]:
            # 意味着在下标为i的地方，最长前缀的长度为j+1，所以如果是在第i+1位匹配失败，意味着最长前缀长度为j+2
            # 所以要继续从下标为j+1（也就是长度j+2）的地方开始继续查找
            i += 1
            j += 1
            next[i] = j
        else:
            # 从前面已经匹配的地方再次查找
            j = next[j]
    return next
def KMP(m: str, s: str) -> int:
    """
    在m中查找n第一次出现的下标
    :param m: 被匹配的长字符串
    :param s: 用来做模式匹配的短字符串
    :return: 返回匹配成功后的起始位置的下标
    """
    next = getNext(s)
    i = 0
    j = 0
    while i < len(m) and j < len(s):
        if j == -1 or m[i] == s[j]:
            i += 1
            j += 1
        else:
            j = next[j]
    if j == len(s):
        return i - j
    return -1
if __name__ == "__main__":
    str1 = 'ababababca'
    str2 = 'bab'
    # print(getNext('abababca'))
    print(KMP(str1, str2))

预防 措施

虽然理论上提高了KMP算法的时间复杂度，但如果子串的重复频率不太高，优化效果就不明显。同时细心的朋友应该也注意到了，有时候当匹配不成功的时候，下一个数组查询会连续进行几次，最后j还是回到了顶部位置，中间重复的下一个查询也是不必要的，所以后面的KMP算法就有了改进， 我们下次再看。

参考

：