字符串匹配算法

---

字符串匹配算法是一个经常使用的算法。具体地说，字符串匹配的任务是：给定一个待搜索的字符串（往往较长，通常称为 haystack），以及一个想要搜索的字符串（往往较短，通常称为 needle），查找 needle 在 haystack 中出现的第一个位置（从 0 开始）。如果不存在，则返回 -1。

特别的，当 needle 为空字符串时，应该返回什么值呢？在 C 语言的 strstr() 以及 Java 的 indexOf() 定义中，此情况下的返回值为0。

问题定义

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

记：$N$ 为 haystack 字符串的长度，$L$ 为 needle 字符串的长度。

Brute force - 暴力法

子串逐一比较

Brute force 方法，也成为暴力法，思路是直接对 haystack 中每个长度等于 needle 的子字符串进行比较，若其内容与 needle 相同，则搜索成功，返回首个字符的索引。如果遍历到字符串结尾仍然未找到结果，则搜索失败，返回 -1。

def strStr(self, haystack: str, needle: str) -> int:
    L, n = len(needle), len(haystack)
    # 当 L == 0 时，会使 haystack[start: start + L] 也为空
    # 因此不必对 L == 0 额外进行判断
    for start in range(n - L + 1):
        if haystack[start: start + L] == needle:
            return start
    return -1

复杂度分析

• 时间复杂度：$O((N - L)L)$。内循环中比较字符串的复杂度为 $L$，总共需要比较 $(N - L)$ 次。

• 空间复杂度：$O(1)$。

双指针

在初始的 Brute force 方法中，由于会将 haystack 所有长度为 L 的子串都与 needle 字符串比较，实际上是不需要这么做的。

首先，只有子串的第一个字符跟 needle 字符串第一个字符相同的时候才需要比较。

其次，可以一个字符一个字符比较，一旦不匹配了就立刻终止。

因此，可以对其进行改进，使用两个指针，算法流程为：

• 移动 pn 指针，直到 pn 所指向位置的字符与 needle 字符串第一个字符相等。

• 通过 pn，pL，curr_len 计算匹配长度。

• 如果完全匹配（即 curr_len == L），返回匹配子串的起始坐标（即 pn - L）。

• 如果不完全匹配，回溯。使 pn = pn - curr_len + 1， pL = 0， curr_len = 0。

def strStr(self, haystack: str, needle: str) -> int:
    L, n = len(needle), len(haystack)
    if L == 0:
        return 0

    pn = 0	# 子串头指针
    while pn < n - L + 1:
        # 待匹配指针
        pL = 0
        # 计算最长的匹配长度
        while pL < L and haystack[pn + pL] == needle[pL]:
            pL += 1
        
        # 如果匹配了 needle 的全部字符，则返回当前子串头指针位置
        if pL == L:
            return pn
        # 否则，头指针后移，继续查找
        pn += 1
        
    return -1

复杂度分析

• 时间复杂度：最坏时间复杂度为 $O((N - L)L)$，最优时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$。

Knuth–Morris–Pratt

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

KMP 算法，是在字符串匹配算法中比较经典的一个算法，它以三个发明者 Knuth-Morris-Pratt 的名称命名，起头的那个 K 就是著名科学家 Donald Knuth。

首先，让我们回顾一下上面的暴力法，暴力法的效率问题主要体现在，当出现位置不匹配时，它会同时回退 haystack 和 needle 的位置，具体地说，haystack 的搜索位置从 pn + pL 回退到 pn，needle 的搜索位置从 pL 回退到 0，这种回退机制导致了算法往往会进行很多不必要的操作。

比如，如果 haystack 为 aaacaaadaaa，而 needle 为 aaaa，算法在第一次会对 aaac 和 aaaa 进行比较，然后第二次对 aaca 和 aaaa 进行比较…这就导致了一个问题，由于 needle 中根本就没有 c 这个字符，所有这几次比较注定是失败的。这也就是暴力法效率差的主要原因。

那么，在 KMP 中，如何利用已知的比较信息，从而不要把“haystack 中的搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

想要做到这一点，需要针对于 needle，产生一个部分匹配表，例如，当 needle 为 ABCDABD 时，部分匹配表如下：

搜索词	A	B	C	D	A	B	D
部分匹配值	0	0	0	0	1	2	0

对于这张表的介绍，以及如何使用，这篇文章已经写的非常清楚，本文中不再赘述

计算部分匹配表

首先，要了解两个概念：“前缀” 和 “后缀”。 “前缀” 指除了最后一个字符以外，一个字符串的全部头部组合；“后缀” 指除了第一个字符以外，一个字符串的全部尾部组合。

“部分匹配值” 就是 “前缀” 和 “后缀” 的最长的共有元素的长度。以 “ABCDABD” 为例：

子串	前缀集	后缀集	共有元素	部分匹配值
A	$\phi$	$\phi$	$\phi$	0
AB	A	B	$\phi$	0
ABC	A, AB	BC, C	$\phi$	0
ABCD	A, AB, ABC	BCD, CD, D	$\phi$	0
ABCDA	A, AB, ABC, ABCD	BCDA, CDA, DA, A	A	1
ABCDAB	A, AB, ABC, ABCD, ABCDA	BCDAB, CDAB, DAB, AB, B	AB	2
ABCDABD	A, AB, ABC, ABCD, ABCDA, ABCDAB	BCDABD, CDABD, DABD, ABD, BD, D	$\phi$	0

“部分匹配” 的实质是，有时候，字符串头部和尾部会有重复。比如，“ABCDAB” 之中有两个 “AB”，那么它的 “部分匹配值” 就是 2（“AB” 的长度）。搜索词移动的时候，第一个 “AB” 向后移动 4 位（字符串长度 - 部分匹配值），就可以来到第二个 “AB” 的位置。

Sunday

https://leetcode-cn.com/problems/implement-strstr/solution/python3-sundayjie-fa-9996-by-tes/

Horspool

https://www.cnblogs.com/cobbliu/archive/2012/05/29/2524244.html

Boyer-Moore

https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

Rabin Karp

https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/