跳转至

串(模式匹配)

模式匹配 在字符串\(s\)中找出与字符串\(t\)相等的子串的操作.其中字符串\(s\)被称为主串或者目标串,\(t\)被称为模式串.

朴素匹配法(BF算法)

算法描述 枚举目标串\(s\)中每一个与模式串\(t\)相等的子串,判断是否匹配;即首先将模式串\(t\)的第0位字符与目标串第0位字符对齐,然后依次对比每个字符,若都相等则匹配成功,否则将t整体后移动一位,然后重新开始匹配.

图示

C++
 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
/**
 * BF（Brute Force）算法实现字符串模式匹配
 * 
 * @param S 主串
 * @param P 模式串
 * @return 如果找到匹配的子串，返回模式串在主串中的起始位置（从0开始）；
 *         如果未找到，返回 -1
 */
int PatternMathBF(const std::string& S, const std::string& P) {
    int m = S.length(); // 主串长度
    int n = P.length(); // 模式串长度

    if (n > m) {
        return -1;
    }

    // 遍历主串，从第0个字符开始，最多到 m - n 的位置
    for (int i = 0; i <= m - n; ++i) {
        int j;

        for (j = 0; j < n; ++j) {
            if (S[i + j] != P[j]) {
                break;
            }
        }

        if (j == n) {
            return i; // 返回匹配的起始位置
        }
    }

    return -1;
}
时间复杂度\(O(nm)\),由于指针会后退所以最坏的情况要遍历主串(n-m)次,遍历模式串(m)次,最大次数为(nm-m^2),所以时间复杂度的上界为\(O(nm)\)

KMP算法