【数据结构】字符串的朴素模式匹配算法-EW帮帮网

字符串匹配是计算机科学中的一个基本问题，特别是在文本处理、搜索引擎、数据挖掘等领域都有广泛的应用。朴素模式匹配（Naive String Matching）是一种非常直观的解决方案，尽管它在效率上并不是最优的，但其简洁性和易懂性使得它成为学习字符串匹配问题的基础。本文将深入探讨朴素模式匹配算法的原理、实现过程以及实际应用。

文章目录

什么是朴素模式匹配？

朴素模式匹配算法用于寻找一个字符串（模式字符串）在另一个字符串（文本字符串）中的所有出现位置。具体而言，给定一个文本串 T 和一个模式串 P，我们要找出 P 在 T 中的所有匹配位置。

例如，考虑文本串 T = "abcabcabc" 和模式串 P = "abc"，我们希望找到所有 P 出现的位置。朴素模式匹配算法将会逐字符对比 P 和 T，如果发现匹配，则记录该位置并继续查找下一个位置，你可以简单的理解为暴力算法的实现。

朴素模式匹配的思路

朴素模式匹配算法的基本思路如下：

遍历文本字符串：从文本字符串 T 的每个位置开始，检查模式字符串 P 是否与该位置的子字符串匹配。
逐字符比较：对于每个位置，逐个字符地将模式字符串 P 与文本字符串 T 的对应部分进行比较。
匹配成功：如果模式字符串 P 在当前位置的子字符串中完全匹配，则记录下该位置。
继续查找：移动到下一个位置，继续执行上述步骤，直到遍历完文本字符串。

示例分析

假设我们有以下的文本字符串 T 和模式字符串 P：

文本字符串 T = "ababcababc"
模式字符串 P = "ababc"

我们希望找出 P 在 T 中的所有匹配位置。为了清晰理解朴素匹配的过程，下面通过字符逐个比较的过程进行说明。

匹配过程：

从位置 0 开始：
- 检查 T[0] 到 T[4] 是否等于 P[0] 到 P[4]：
  - T[0] = 'a', P[0] = 'a' → 匹配
  - T[1] = 'b', P[1] = 'b' → 匹配
  - T[2] = 'a', P[2] = 'a' → 匹配
  - T[3] = 'b', P[3] = 'b' → 匹配
  - T[4] = 'c', P[4] = 'c' → 匹配
- 所以，模式串 P 在位置 0 的子串 T[0..4] 完全匹配。
记录匹配位置：位置 0
从位置 1 开始：
- 检查 T[1] 到 T[5] 是否等于 P[0] 到 P[4]：
  - T[1] = 'b', P[0] = 'a' → 不匹配
- 因为首字符不匹配，模式串 P 向后移动一位，继续检查下一个位置。
从位置 2 开始：
- 检查 T[2] 到 T[6] 是否等于 P[0] 到 P[4]：
  - T[2] = 'a', P[0] = 'a' → 匹配
  - T[3] = 'b', P[1] = 'b' → 匹配
  - T[4] = 'a', P[2] = 'a' → 匹配
  - T[5] = 'b', P[3] = 'b' → 匹配
  - T[6] = 'c', P[4] = 'c' → 匹配
- 所以，模式串 P 在位置 2 的子串 T[2..6] 完全匹配。
记录匹配位置：位置 2
从位置 3 开始：
- 检查 T[3] 到 T[7] 是否等于 P[0] 到 P[4]：
  - T[3] = 'b', P[0] = 'a' → 不匹配
- 因为首字符不匹配，模式串 P 向后移动一位，继续检查下一个位置。
从位置 4 开始：
- 检查 T[4] 到 T[8] 是否等于 P[0] 到 P[4]：
  - T[4] = 'c', P[0] = 'a' → 不匹配
- 因为首字符不匹配，模式串 P 向后移动一位，继续检查下一个位置。
从位置 5 开始：
- 检查 T[5] 到 T[9] 是否等于 P[0] 到 P[4]：
  - T[5] = 'a', P[0] = 'a' → 匹配
  - T[6] = 'b', P[1] = 'b' → 匹配
  - T[7] = 'a', P[2] = 'a' → 匹配
  - T[8] = 'b', P[3] = 'b' → 匹配
  - T[9] = 'c', P[4] = 'c' → 匹配
- 所以，模式串 P 在位置 5 的子串 T[5..9] 完全匹配。
记录匹配位置：位置 5

结果

最终，模式串 P = "ababc" 在文本串 T = "ababcababc" 中的匹配位置为：[0, 2, 5]。

朴素模式匹配的算法实现

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

// 朴素模式匹配函数
vector<int> naiveStringMatch(const string &text, const string &pattern) {
    vector<int> result;
    int n = text.length();
    int m = pattern.length();
    
    // 遍历文本串的每一个位置
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // 比较文本串的子串和模式串
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        // 如果整个模式串匹配成功
        if (j == m) {
            result.push_back(i);  // 记录匹配位置
        }
    }
    return result;
}

int main() {
    string text = "abcabcabc";
    string pattern = "abc";
    vector<int> matches = naiveStringMatch(text, pattern);
    // 输出所有匹配位置
    cout << "Pattern found at positions: ";
    for (int pos : matches) {
        cout << pos << " ";
    }
    cout << endl;
    return 0;
}

代码解析

naiveStringMatch 函数接收两个参数，text 和 pattern，分别代表文本串和模式串。
我们通过两层循环来进行比较。外层循环遍历文本串的每个位置，内层循环逐字符与模式串进行比较。
如果所有字符都匹配，则记录下匹配的位置。
最后，返回所有匹配位置的索引。

底层原理和时间复杂度分析

朴素模式匹配的时间复杂度是 O(n * m)，其中 n 是文本串的长度，m 是模式串的长度。原因如下：

外层循环需要遍历文本串的每一个位置，共有 n - m + 1 个位置。
对于每个位置，内层循环最多需要比较 m 次字符，最坏情况下每个位置都需要进行完全的逐字符比较。

因此，最坏情况下的时间复杂度是 O(n * m)。

虽然时间复杂度较高，但朴素模式匹配算法实现简单、直观，因此在很多简单的应用场景中仍然有效。

边界情况

边界情况：在实现朴素模式匹配时，应该特别注意文本串长度 n 小于模式串长度 m 的情况。在这种情况下，显然没有匹配的可能，算法应提前退出。
空字符串：如果文本串或模式串为空，应该返回一个空的匹配结果。
大小写敏感性：算法的实现默认是大小写敏感的。如果需要忽略大小写，可以在比较时统一转换成小写或大写。
模式串的重复字符：当模式串包含重复字符时，虽然会增加无效的比较次数，但朴素算法并不会做任何优化。在实际应用中，可以通过更高级的算法（如 KMP 算法）来提高效率。

算法的优化：KMP 算法

虽然朴素模式匹配算法简单易懂，但它的效率较低，尤其是在文本较长、模式串较长的情况下。为了提高效率，可以使用 KMP（Knuth-Morris-Pratt）算法。

KMP算法通过构建一个 部分匹配表（又称“失配表”）来避免重复的字符比较，从而将时间复杂度降低到 O(n + m)。这使得它在大规模数据处理中具有显著的性能优势。

我们会在后续介绍KMP算法的实现原理，敬请关注

总结

朴素模式匹配算法是学习字符串匹配问题时的重要起点。虽然它的时间复杂度比较高，但其简单的实现方式在小规模应用中仍然有效果。我们先简单理解朴素算法，后续我们将会使用更复杂的算法（如 KMP 算法）来优化字符匹配的性能。

【数据结构】字符串的朴素模式匹配算法