字符串匹配算法

字符串匹配算法

exdoubled Lv2
  2025-09-24 17:00 2025-09-24 17:00 Created   2025-09-24 23:17:14 2025-09-24 23:17:14 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 中的字符串匹配算法

待整理

On this page
字符串匹配算法
  1. 字符串匹配算法
    1. BF 算法
      1. 逻辑梳理
      2. 代码实现
    2. KR 算法
      1. 代码实现
    3. KMP 算法
      1. 逻辑梳理
      2. 前缀函数
      3. KMP 算法的多次匹配
      4. 代码实现
    4. BM算法
      1. 最后出现位置表——BC 表
      2. Galil 规则
    5. STL 中的字符串匹配算法