字符串匹配——KMP算法

一、专业名词解释及其原理

1. BF算法

BF算法，即暴力 (Brute Force)算法，是普通的 模式匹配 算法

从原串（长度M）的第一个字符开始，将子串（长度N）与原串的每个字符依次进行匹配，若匹配不成功，则从原串的下一个字符开始，直至匹配成功。

时间复杂度：O(M·N)

2. KMP算法

KMP算法是在 Brute-Force 算法的基础上同时提出的模式匹配的改进算法，
不同于BF算法，KMP在字符串匹配过程中并非是一个一个字符去比对，而是有一个跨越的过程，而这个跨越的过程依靠的正是next数组

匹配过程：

进行匹配，我们发现，到下标4时失配，可以直接将子串移动到下标为4的位置，现在看它的next值为2，意味着它前方的字符串的长度为2的前缀和后缀相等，并且在原串中这前方的字符串已经匹配上了，我们可以直接将子串字符前方字符串的前缀对应上原串字符前方的字符串的后缀，因此我们还要向前移动两格，移动到下标为2的位置然后从4开始进行匹配，即4之前的2个元素已经匹配好了无须进行匹配，我们现在只要从4开始往后进行匹配即可

随后重复此过程直至匹配上即可

3. next数组

子串中的每一个字符对应一个next数组中的一个数字，这个数字就表示这个字符的前面字符串的最长公共前后缀

• 子串中第一个字符前方没有字符串，其next值规定为-1
• 子串中第二个字符前方仅有一个字符，并无前后缀，其next值规定为0

特殊情况下的next数组：

4. 最长公共前后缀

即一个字符串他的前缀和后缀相等的时候，前后缀的长度最长是多少

如：现在要求箭头指的字符的next数组中的数，故要求前方字符串aba的最长公共前后缀，从1开始看，当前后缀长度为1时，前缀和后缀都为a，因此成立，随后往后增加到直至没有前后缀，当前后缀长度为2时，前缀为ab 而后缀为ba，不相等，因此，最长公共前后缀为1，故next数组中箭头字符下方的数字为1

5.nextVal数组

对next数组的一次优化，在nextVal数组中，原有的next值通常会变小，这也意味着跨越的距离会变大，即匹配的速度更快
现在有一个子串及其next数组，需要将其next数组优化为nextVal数组

优化过程：

现在要求b的nextVal值，可以先其找next值，然后找到next值对应的index的元素a，看这个元素a是否与原来要求nextVal值的元素b相等，若相等则把元素a的nextVal值拿过来，反之则不优化，保留其原来的next值为nextVal值，不进行优化，而这边的答案显然是a≠b，因此不进行优化，直接把上面的next值 0 拿下来

优化后：

原理：

比如说在匹配过程中，下标为2的字符失配了，next数组的处理方法是将原来的a（这里的下标也可以表示失配后重新开始的位置）又拿过来进行匹配，结果显而易见是匹配失败的，而nextVal数组中是看这个失配的元素与下标元素是否相等，如果相等则没有必要去匹配了 这里必然是失配的，若不相等则说明匹配还有意义，nextVal数组就相当于将next数组错配处理的过程直接快进到底

二、代码实现

1.计算next数组

机算的过程和手算的过程不同，这是一个逐渐往里面加字符的过程，每加一个字符，就根据其前一个字符的next值求出其next值，那么这个next值到底是如何求的呢？

注：在next值的计算过程中，下一个next值相较与前一个加最多只能加1，减最多只能减到0

？就是我们要加进来的字符，并且我们要看其与前缀后一个字符的关系，这关乎于？的next值是做加法还是做减法，若？值与这个字符相等，则加1（最多只能加1）next[i] = next[i - 1] + 1，反之，做减法，至于减多少可以看他的前缀的最长公共前后缀，这可以通过next[6]取到，直至找到相等的字符并取出其下标加1即为其next值，若是一直没有找到相等字符，next[i] = next[0] + 1即0，这个过程类似于DP

def get_next(p: str) -> list:
    """
    get the next array
    :param p: substring
    :return: next array
    """
    if not p:
        return []
    if len(p) == 1:
        return [-1]
    if len(p) == 2:
        return [-1, 0]

    nextArr = [0] * len(p)
    nextArr[0] = -1
    nextArr[1] = 0

    for i in range(2, len(p)):
        newChar = p[i - 1]  # ?
        # 看新字符是否与最长公共前后缀的前缀的后一个字符相等
        if newChar == p[nextArr[i - 1]]:
            nextArr[i] = nextArr[i - 1] + 1
        else:
            cur = nextArr[nextArr[i - 1]]  # 记录最长公共前后缀的前缀的后一个字符的下标
            while newChar != p[cur]:
                cur = nextArr[cur]  # 继续往前跳
                if cur == -1:
                    break
            nextArr[i] = cur + 1

    return nextArr

2.next数组 -> nextVal数组

# 转换next数组为nextVal数组
def next_to_val(p: str, nextArr: list) -> list:
    if len(nextArr) <= 1:
        return nextArr

    nextVal = [0] * len(nextArr)
    nextVal[0] = -1

    for i in range(1, len(nextArr)):
        if p[i] == p[nextArr[i]]:
            nextVal[i] = nextVal[nextArr[i]]
        else:  # 优化
            nextVal[i] = nextArr[i]

    return nextVal

3.KMP算法主方法

def KMP(s: str, p: str) -> int:
    # 初始化指针，i指向s，j指向p
    i = j = 0
    nextArr = get_next(p)
    nextVal = next_to_val(p, nextArr)

    # 保证指针不越界
    while i < len(s) and j < len(p):
        if s[i] == p[j]:
            i += 1
            j += 1
        else:
            j = nextVal[j]
            if j == -1:
                j = 0
                i += 1
    # 如果是j越界就说明匹配上了，返回其位置，反之未匹配上返回-1
    return i - len(p) if j >= len(p) else -1