数据结构与算法 - 字符串匹配

发表于 2020-05-17 更新于 2021-11-07 分类于数据结构与算法

1. 题目介绍

详见: https://leetcode-cn.com/problems/implement-strstr/

2. 解题方法 1 - 暴力解法

2.1 算法实现

暴力算法比较容易理解:

首先将主串和子串头部对齐
按位遍历比较子串和主串是否一致
如果不一致, 则将子串向后移动一位, 重新遍历

图示如下 ^[1]:

代码如下:

#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) {
        int haylength = haystack.length();
        int nedlength = needle.length();
        for(int i = 0; i <= haylength - nedlength; i++)
        {
            int j = 0;
            for(j = 0; j < nedlength; j++)
            {
                if(haystack[i+j] != needle[j]) break;
            }
            if(j == nedlength) return i;
        }
        return -1;
    }
};

2.2 算法分析

假设主串长度为 N, 子串长度为 M, 则

时间复杂度：最坏时间复杂度为 O((N - M)M)，最优时间复杂度为 O(M)

空间复杂度：O(1)

3. 解题方法 2 - KMP 算法

3.1 KMP 算法背景

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个 文本串 S 内查找一个 模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。^[2]

3.2 KMP 算法实现

KMP 算法思想

KMP 算法对暴力算法进行了改进, 在遍历文本串和模式串时, 如如果发现不一致的位, KMP 算法不会像暴力算法一样只将模式串向后移动 1 位, 而是会跳过一些不可能的位置, 直接将模式串后移 K 位

首先将文本串和模式串头部对齐
按位遍历比较模式串和文本串是否一致
如果不一致, 则将模式串向后 K 位, 并从文本串的位置继续遍历

图示如下:

从图中可知, KMP 算法可以避免指向文本串的指针的回溯, 从而提高寻找子串的效率

而需要跳过多少个字符呢? (也就是如何的到 K 的值呢?) 这就是 KMP 算法的精髓所在了, 在 KMP 算法中, K 值被称为 next 数组, 是一个只和模式串有关的数组, 下面我们就来分析下 next 数组的求法

如何求得 K (next 数组的求法)

next 数组的值是代表着字符串的前缀与后缀相同的最大长度 ^[?], 前缀指除了最后一个字符以外，一个字符串的全部头部组合；后缀指除了第一个字符以外，一个字符串的全部尾部组合。

[?] 大多数博文都是这个么写的, 但没有找到详细的证明

以模式串 ABBAB 为例前缀与后缀相同的最大长度为 2, 即该模式串的 next 数组的值为 2.

以模式串为 array:ABBABAABB 为例, n 为字符串的下标

初始值:

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	?	?	?	?	?	?	?	?	?

下标 0: 情况 1

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	?	?	?	?	?	?	?	?

下标 1: 情况 3

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	?	?	?	?	?	?	?

下标 2: 情况 3

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	?	?	?	?	?	?

下标 3: 情况 2

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	1	?	?	?	?	?

下标 4: 情况 2

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	1	2	?	?	?	?

下标 5: 情况 3

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	1	2	1	?	?	?

下标 6: 情况 3

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	1	2	1	1	?	?

下标 7: 情况 2

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	1	2	1	1	2	?

下标 8: 情况 2

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	0	0	0	1	2	1	1	2	3

最后将 next 数组向右移动一格, 并将起始位置 - 1 (方便程序编写, 建议结合代码理解为什么要进行这一步操作)

模式串	A	B	B	A	B	A	A	B	B
下标	0	1	2	3	4	5	6	7	8
next	-1	0	0	0	1	2	1	1	2

情况 1

n == 0

如果模式串的首位即与不匹配, 即无前缀和后缀, 则认为前缀和后缀相同的最大长度为 0, 即 next[0] = 0

情况 2

array[n] == array[next(n-1)]

由 next 数组定义得: array[0 ~ next(n-1)-1] ≡ array[n-next(n-1) ~ n-1]

∴ array[next(n-1)] == array[n]

∴ array[0 ~ next(n-1)] ≡ array[n-next(n-1) ~ n]

∴ next[n] = next(n-1) + 1

情况 3^[?]

[?] 证明不是很严谨, 未找到严谨的证明方法

array[n] != array[next(n-1)]

定义: k = next(n-1)

由 next 数组定义得:

array[0 ~ k-1] ≡ array[n-k ~ n-1]

array[0 ~ next(k-1)-1] ≡ array[k-next(k-1) ~ k-1]

∴ array[0 ~ next(k-1)-1] ≡ array[n-k+(k-next(k-1)) ~ n-1]

∴ array[0 ~ next(k-1)-1] ≡ array[n-next(k-1) ~ n-1]

如果: array[next(k-1)] == array[n]

则: array[0 ~ next(k-1)] ≡ array[n-next(k-1) ~ n]

∴ next[n] = next(k-1)

如果: array[next(k-1)] != array[n]

//TODO

KMP 算法完整实现

#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) {
        int haylength = haystack.length();
        int nedlength = needle.length();

        /* 特殊情况处理 */
        if(0 == nedlength) return 0;
        if(0 == haylength) return -1;

        int i = 0;
        int j = -1;

        /* 计算 next 数组 */
        vector<int> next;
        next.resize(nedlength);
        next[0] = -1;
        while(i < nedlength - 1)
        {
            if(j == -1 || needle[i] == needle[j]) next[++i] = ++j;
            else j = next[j];
        }

        i = 0;
        j = 0;

        /* KMP 算法 */
        while((i < haylength) && (j < nedlength))
        {
            if(j == -1 || haystack[i] == needle[j]) { i++; j++; }
            else j = next[j];
        }
        if(j == nedlength) return i - j;
        else return -1;
    }
};

3.3 KMP 算法分析

假设主串长度为 N, 子串长度为 M, 则

时间复杂度：最坏时间复杂度为 O(N + M)，最优时间复杂度为 O(M)

空间复杂度：O(N)

4. 解题方法 3 - Rabin Karp 算法

4.1 abin Karp 算法背景

Michael O. Rabin 和 Richard M. Karp 在 1987 年提出一个想法，即可以对模式串进行哈希运算并将其哈希值与文本中子串的哈希值进行比对。总的来说这一想法非常浅显，唯一的问题在于我们需要找到一个哈希函数，它需要能够对不同的字符串返回不同的哈希值。例如，该哈希函数可能会对每个字符的 ASCII 码进行算，但同时我们也需要仔细考虑对多语种文本的支持。

4.2 abin Karp 算法实现

abin Karp 算法思想

Rabin Karp 算法也是对暴力算法的改进, 在比较文本串和模式串时, 暴力算法需要比较 O(M)* 次, 如果采用哈希运算的话, 就可以把比较降低为 O(1) 次:

假设文本串的长度为 N, 模式串的长度为 M

计算模式串的 Hash 值 - O(M)
计算文本串中第一个个与模式串长度一致的子串的 Hash 值 - O(m)
如果两个 Hash 值不一致, 则将计算文本串的下一个子串 Hash 值 - O(1), 并再次进行比较...
如果两个 Hash 值一致, 则将两个子串进行一次完整比较, 确认两个字符串完全一致

Hash 算法的选择

由于需要在 O(1) 的事件复杂度内计算出两个相邻子串的 Hash 值, 故基本不能使用各语言标准库中自带的 Hash 函数, 需要自己设计一个可以递推的 Hash 函数

常见的 Hash 算法 - 取模

比如一个字符串 ABCDE, 他的 Hash 值为:

Hash(ABCDE) = ( A * 31^4 + B * 31^3 + C * 31^2 + D * 31^1 + E ) % 100000

abin Karp 算法完整实现

#include<string>
#include<vector>
using namespace std;

class Solution {
private:
    int BASE = 10000;
    int DIFF = 1;
public:
    int strStr(string haystack, string needle) {
        int haylength = haystack.length();
        int nedlength = needle.length();
        if(0 == nedlength) return 0;
        if(0 == haylength) return -1;

        int nedhash = 0;
        for(auto a : needle)
        {
            nedhash = (nedhash * 31 + a) % BASE;
            DIFF = (DIFF * 31) % BASE;
        }

        int hayhash = 0;
        for(int i = 0; i < nedlength; i++)
            hayhash = (hayhash * 31 + haystack[i]) % BASE;

        for(int i = 0; i <= haylength - nedlength; i++)
        {
            if(0 != i)
            {
                hayhash = (hayhash * 31 + haystack[i + nedlength - 1]) % BASE;
                hayhash = hayhash - (DIFF * haystack[i - 1])  % BASE;
                if(hayhash < 0) hayhash += BASE;
            }
            /* 两个 Hash 值一致, 则将两个子串进行一次完整比较 */
            if(hayhash == nedhash)
            {
                int j = 0;
                for(j = 0; j < nedlength; j++)
                    if(haystack[i + j] != needle[j]) break;
                if(j == nedlength) return i;
            }
        }
        return -1;
    }
};

4.3 abin Karp 算法分析

假设主串长度为 N, 子串长度为 M, 则

时间复杂度：最坏时间复杂度为 O((N - M)M)，最优时间复杂度为 O(M)

空间复杂度：O(1)

何照江的博客

数据结构与算法 - 字符串匹配

1. 题目介绍

2. 解题方法 1 - 暴力解法

2.1 算法实现

2.2 算法分析

3. 解题方法 2 - KMP 算法

3.1 KMP 算法背景

3.2 KMP 算法实现

KMP 算法思想

如何求得 K (next 数组的求法)

情况 1

情况 2

情况 3^[?]

KMP 算法完整实现

3.3 KMP 算法分析

4. 解题方法 3 - Rabin Karp 算法

4.1 abin Karp 算法背景

4.2 abin Karp 算法实现

abin Karp 算法思想

Hash 算法的选择

常见的 Hash 算法 - 取模

abin Karp 算法完整实现

4.3 abin Karp 算法分析

5. 参考文献

1. 题目介绍

2. 解题方法 1 - 暴力解法

2.1 算法实现

2.2 算法分析

3. 解题方法 2 - KMP 算法

3.1 KMP 算法背景

3.2 KMP 算法实现

KMP 算法思想

如何求得 K (next 数组的求法)

情况 1

情况 2

情况 3[?]

KMP 算法完整实现

3.3 KMP 算法分析

4. 解题方法 3 - Rabin Karp 算法

4.1 abin Karp 算法背景

4.2 abin Karp 算法实现

abin Karp 算法思想

Hash 算法的选择

常见的 Hash 算法 - 取模

abin Karp 算法完整实现

4.3 abin Karp 算法分析

5. 参考文献

情况 3^[?]