字符串匹配算法

字符串匹配算法

exdoubled Lv3
  2025-09-24 17:00 2025-09-24 17:00 Created   2025-10-22 10:37:45 2025-10-22 10:37:45 Updated    1.5k Words  6 Mins  

假设主串（文本串）是一个长度为的字符串，子串（模式串）是一个长度为的字符串，我们的目的是要从中匹配到

BF 算法

最朴素的串模式匹配算法

逻辑梳理

滑动窗口的做法

设主串（文本串）匹配到位置，子串匹配到位置

  • 如果，，继续匹配下一个字符
  • 如果，，也就是失配就回溯

代码实现

1
2
3
4
5
6
7
8
9
int BF(string A, string B){
    int n = A.size();
    int m = B.size();
    for(int i = 0; i <= n - m; ++i) {
        string temp = A.substr(i, m);
        if(temp == B) return i;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
int BF(string A, string B) {
    int n = A.size();
    int m = B.size();
    // 滑动窗口
    for(int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && A[i + j] == B[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

优点：不需要预处理，固定存储空间，算法复杂度

缺点：最坏复杂度高

KR 算法

将个字符的比较变为一个哈希值的比较

算法效率取决于哈希函数的选取

定义哈希函数或者

其中为一个整数，为一个大整数

冷知识：实际使用时只取后几位的二进制的哈希函数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int KR(string A, string B){
    int n = A.size();
    int m = B.size();
    
    int k = 256; // 基数
    int p = 1000000007; // 大质数
    long long B_hash = 0;
    for(int i = 0; i < m; ++i) B_hash = (B_hash * k + B[i]) % p;
    
    long long At_hash = 0;
    long long power = 1; // 用于存储 k^(m-1) mod p
    
    for(int i = 0; i < m; ++i){
        At_hash = (At_hash * k + A[i]) % p;
        if(i < m-1) power = (power * k) % p;
    }
    
    // 滑动窗口
    for(int i = 0; i <= n-m; ++i){
        if(B_hash == At_hash) return i;
        /*
        // 避免 hash 冲突
        if(B_hash == At_hash){
        	bool key = true;
        	for(int j = 0; j < m; ++j){
        		if(A[i+j] != B[j]){
        			key = false;
        			break;
        		}
        	}
        	if(key) return i;
        }
        */
        if(i < n-m){
            At_hash = (At_hash - A[i] * power % p + p) % p;
            At_hash = (At_hash * k + A[i+m]) % p;
        }
    }
    return -1;
}

KMP 算法

KMP 算法发现每个字符对应的该值仅依赖于模式本身，与目标对象无关

逻辑梳理

设主串（文本串）匹配到位置，子串匹配到位置

  • 如果或者，，继续匹配下一个字符

  • 如果且，不变，

    这一步相当于子串向右移动实际位数为

前缀函数

长度为的字符串前缀函数为数组

其中定义为字串最长的相等的真前缀和真后缀的长度

即

规定

：字符串

最长相等的真前缀真后缀为

最长相等的真前缀真后缀为

无相等的真前缀真后缀

计算前缀函数的方法

推导：如果第位失配时，怎么求

  • 如果显然

  • 如果

    由数组的含义，我们知道

    与相等的，记此时

    此时的最长真前缀真后缀相等的字符串与的最长真前缀真后缀相等的字符串相同，记这个字符串为

    是的真前缀，那么它是的真前缀，是的真后缀，那么它是的真后缀

    假如存在一个比长的的既是真前缀也是真后缀的字符串，记为

    那么是的真前缀，的真后缀，由知是的真后缀，这与的最大性矛盾，故是最长的相等的真前缀真后缀字符串

    根据数组的含义

    容易知道，那么

  • 当时，和第一种情况合并

1
2
3
4
5
6
7
8
9
10
11
vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n-1){
        if(k == -1 || s[i] == s[k]) next[++i] == ++k;
        else k = next[k];
    }
    return next;
}

数组含义：

  • 当前字符串中，最大长度相同真前缀和真后缀
  • 发生失配时，下一步匹配时子串跳到的位置，如果，则跳到子串的位置

KMP 算法的多次匹配

如果要搜索的字符串匹配段有重叠的情况，匹配成功时，子串后移整个子串的最大公共真前缀和真后缀长度，和文本串的下一位继续匹配

代码实现

单次匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n+1);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n){
        while(k != -1 && s[i] != s[k]) k == next[k];
        ++i;++k;
        if(s[i] == s[k]) next[i] = next[k];
        else next[i] = k;
    }
    return next;
}

int KMP(string A, string B){
    int n = A.size();
    int m = B.size();
    vector<int> next = getNext(A);
    int i = 0,j = 0;
    while(i < n){
        while(j != -1 && A[i] != B[j]) j = next[j];
        ++i;++j;
        if(j >= m) return i - j;
    }
    return -1;
}

多次匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n+1);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n){
        while(k != -1 && s[i] != s[k]) k == next[k];
        ++i;++k;
        if(s[i] == s[k]) next[i] = next[k];
        else next[i] = k;
    }
    return next;
}

int KMP(string A, string B){
    int n = A.size();
    int m = B.size();
    vector<int> next = getNext(A);
    int i = 0, j = 0, ans = 0;
    while(i < n){
        while(j != -1 && A[i] != B[j]) j = next[j];
        ++i;++j;
        if(j >= m){
            ++ans;
            j = next[j];
        }
    }
    return ans;
}

预处理需要的时间和空间

算法时间复杂度

查找阶段最大比较次数

热知识：实际运用中 KMP 算法会比 BM 算法慢

冷知识：实际运用中 KMP 算法绝大多数情况会比 BF 算法慢

为 KMP 算法定制的字符数据中绝大多数情况会比 KR 算法慢

KMP 可以在 AC 自动机（KMP + Trie 树）中使用

BM算法

从右向左匹配字串

两大启发式规则：

  • 坏字符规则：利用第一个不匹配的字符（坏字符）在子串中的位置信息，尝试进行大跨度跳跃，目标是对齐可能匹配的字符
  • 好后缀规则：利用匹配成功的后缀的信息，尝试进行大跨度跳跃，目标是对齐可能匹配的后缀子串

待整理

最后出现位置表——BC 表

预处理需要的时间和空间

算法时间复杂度最坏为，最好为

Galil 规则

STL 中的字符串匹配算法

待整理

  • Title: 字符串匹配算法
  • Author: exdoubled
  • Created at : 2025-09-24 17:00:00
  • Updated at : 2025-10-22 10:37:45
  • Link: https://github.com/exdoubled/exdoubled.github.io.git/sjjg/sjjg02/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
字符串匹配算法
  1. BF 算法
    1. 逻辑梳理
    2. 代码实现
  2. KR 算法
    1. 代码实现
  3. KMP 算法
    1. 逻辑梳理
    2. 前缀函数
    3. KMP 算法的多次匹配
    4. 代码实现
  4. BM算法
    1. 最后出现位置表——BC 表
    2. Galil 规则
  5. STL 中的字符串匹配算法