字符串朴素匹配

1 一句话算法

朴素匹配就是枚举主串中的每个起点，然后从左到右尝试把模式串完整贴上去。

2 问题模型

给定两个字符串：

主串 text，长度为 $n$ ；
模式串 pattern，长度为 $m$ 。

要求找出 pattern 在 text 中出现的所有起始位置。如果只关心第一次出现，返回第一个位置即可。

例如：

1
2

text    = abababaca
pattern = aba

pattern 在 text 中从位置 0、2 和 4 开始出现。

3 核心直觉

把模式串想成一把长度为 $m$ 的尺子。

我们把尺子依次放在 text 的每个可能起点：

text:    a b a b a b a c a
pattern: a b a
         ^

text:    a b a b a b a c a
pattern:   a b a
           ^

每放一次，就逐字符比较：

全部相等：这个起点是一次匹配。
中途不同：这个起点失败，换下一个起点。

朴素匹配不保存任何失配信息，所以失败后只能把起点右移一格。

4 算法步骤

枚举起点 start = 0, 1, ..., n - m。
从 pattern[0] 开始逐字符比较。
若 text[start + j] == pattern[j]，继续比较下一位。
若出现不相等，当前起点失败。
若比较完 $m$ 个字符都相等，记录 start。

5 算法证明

核心不变量：外层循环枚举过的每一个起点，都已经被完整判断过“能不能匹配”。

对固定起点 start，算法逐一比较：

$text[start+j]\quad \text{和}\quad pattern[j]$
其中 $0\le j<m$ 。
如果某个 $j$ 不相等，那么根据字符串相等的定义，当前位置不可能是一次匹配。
如果所有 $j$ 都相等，则：

$text[start,start+m-1] = pattern[0,m-1]$
所以 start 必然是一次匹配。
外层循环覆盖了所有可能起点 $0$ 到 $n-m$ 。

因此算法能找出所有匹配位置。

6 复杂度分析

时间复杂度：最坏 $O(nm)$ 。
空间复杂度：除输出数组外为 $O(1)$ 。

最坏情况常见于大量前缀相同、最后一位才失配的字符串，例如：

1
2

text    = aaaaaaaaaab
pattern = aaaab

7 代码实现

C++
Python

#include <bits/stdc++.h>
using namespace std;

vector<int> brute_force_match(const string &text, const string &pattern) {
    vector<int> positions;
    int n = (int)text.size();
    int m = (int)pattern.size();

    if (m == 0) return positions;

    for (int start = 0; start + m <= n; start++) {
        int matched = 0;
        while (matched < m && text[start + matched] == pattern[matched]) {
            matched++;
        }
        if (matched == m) positions.push_back(start);
    }

    return positions;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;

    vector<int> positions = brute_force_match(text, pattern);
    if (positions.empty()) {
        cout << -1 << "\n";
        return 0;
    }

    for (int i = 0; i < (int)positions.size(); i++) {
        if (i) cout << ' ';
        cout << positions[i];
    }
    cout << "\n";

    return 0;
}

# 暴力字符串匹配：返回 pattern 在 text 中每次出现的起始下标（0-based）。
# 空模式直接返回空列表（与 C++ 版一致），不做"处处匹配"的特判。
# 复杂度 O(n * m)；Python 的 str 下标越界会抛异常，所以循环上界必须先算好。

Positions = list[int]  # 匹配起点列表，0-based 升序


def brute_force_match(text: str, pattern: str) -> Positions:
    """返回所有出现位置的升序列表；text 为空或 pattern 比 text 长时返回空列表。"""
    positions: Positions = []
    n = len(text)
    m = len(pattern)

    if m == 0:
        return positions

    # range(n - m + 1) 等价于 C++ 的 start + m <= n，保证 start + matched 不越界。
    for start in range(n - m + 1):
        matched = 0
        while matched < m and text[start + matched] == pattern[matched]:
            matched += 1
        if matched == m:
            positions.append(start)

    return positions


if __name__ == "__main__":
    import sys
    data = sys.stdin.read().split()
    if len(data) >= 2:
        result = brute_force_match(data[0], data[1])
        print(" ".join(map(str, result)) if result else -1)

Python 模板文件也包含命令行入口，可直接运行；输入输出与 C++ 相同。

8 测试用例

输入：

abababaca aba

输出：

0 2 4

解释：aba 分别从下标 0、2、4 开始出现。

9 应用分类详解

朴素匹配的本质是：不做预处理，不保存失配信息，直接检查每一个候选起点。它适合规模小、实现成本要极低、或作为更高级字符串算法的对照基线。

一、小数据字符串查找

典型模式： $n,m$ 很小，或者测试次数很少。

识别信号： 数据范围只有几百、几千，题目重点不在字符串算法本身。

核心建模： 直接枚举每个起点并逐字符验证。

应用场景	经典题目	核心思路
判断子串是否出现	LeetCode 28	小数据可直接暴力
枚举固定模板	luogu P1308: [NOIP 2011 普及组] 统计单词数	先统一大小写和边界，再顺序扫描

二、二维或特殊形态匹配的起点枚举

典型模式： 需要在网格、矩阵、棋盘上寻找某个形状。

识别信号： 出现“从每个格子出发”“八个方向”“匹配一个单词或图案”。

核心建模： 外层枚举起点，内层按方向或形状逐项检查。

应用场景	经典题目	核心思路
网格单词搜索	LeetCode 79	起点枚举加 DFS
八方向单词匹配	luogu P1101: 单词方阵	枚举起点和方向

三、高级算法的对照基线

典型模式： 需要理解 KMP、哈希、AC 自动机为什么更快。

识别信号： 题目讨论“失配后如何移动”“多模式匹配”“大量查询”。

核心建模： 朴素匹配每次失配都会丢掉已经比较过的信息，高级算法的价值就在于复用这些信息。

应用场景	经典题目	核心思路
KMP 入门前置	luogu P3375: 【模板】KMP	先理解暴力失配为什么慢
字符串哈希对照	luogu P3370: 【模板】字符串哈希	暴力比较可作为小数据校验

10 经典例题

1. LeetCode 28

要求返回模式串第一次出现的位置。朴素匹配是最直接做法，也是理解 KMP 前必须掌握的基线。

2. luogu P1308: [NOIP 2011 普及组] 统计单词数

统计一个单词在文章中出现的次数，并要求匹配完整单词。重点不在字符串匹配算法，而在大小写和单词边界处理。

3. luogu P1101: 单词方阵

在字符矩阵中寻找固定单词。虽然不是一维字符串，但核心仍然是“枚举起点，再检查模式”。

11 参考

旧版文章：Rbook_ejs_old/book/string/brute-force/index.md
后续学习：KMP 算法会复用失配前的信息，避免文本指针回头。

12 相关题解

暂无相关题解