字符串匹配

形式化题目

给定模式串 $S$ 、大小写敏感选项（0 不敏感，1 敏感）和多行文本，按输入顺序输出所有包含模式串的文本行。大小写不敏感时，同一字母的大小写视为相同字符。

思路

先看手写逐位置比较的暴力：

cpp

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:54
 */
// brute.cpp：小数据暴力解，枚举文本中的每个起点并逐字符比较。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string pattern;
    int sensitive;
    int n;
    cin >> pattern >> sensitive >> n;

    for (int i = 0; i < n; i++) {
        string text;
        cin >> text;
        bool found = false;
        for (int start = 0; start + (int)pattern.size() <= (int)text.size(); start++) {
            bool same = true;
            for (int j = 0; j < (int)pattern.size(); j++) {
                char left = text[start + j];
                char right = pattern[j];
                if (!sensitive) {
                    if ('A' <= left && left <= 'Z') {
                        left = char(left - 'A' + 'a');
                    }
                    if ('A' <= right && right <= 'Z') {
                        right = char(right - 'A' + 'a');
                    }
                }
                if (left != right) {
                    same = false;
                    break;
                }
            }
            if (same) {
                found = true;
                break;
            }
        }
        if (found) {
            cout << text << '\n';
        }
    }

    return 0;
}

每一行独立判断，不需要保存全部文本。大小写不敏感时，先把模式串和当前文本都转换为小写，再调用 find() 判断模式串是否出现；大小写敏感时直接查找原字符串。输出时保留原始文本行。

处理流程

以样例为例，模式串 Hello，敏感选项为 1：

文本行	包含 `Hello`?	输出
HelloWorld	是	输出
HiHiHelloHiHi	是	输出
GrepIsAGreatTool	否	-
HELLO	否（大小写敏感）	-
HELLOisNOTHello	是	输出

若把敏感选项改为 0，第 4 行 HELLO 转成小写 hello 后也能匹配，应当输出。

代码

cpp

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
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:54
 */
#include <bits/stdc++.h>
using namespace std;

string lower_copy(string text) {
    for (int i = 0; i < (int)text.size(); i++) {
        if ('A' <= text[i] && text[i] <= 'Z') {
            text[i] = char(text[i] - 'A' + 'a');
        }
    }
    return text;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string pattern;
    int sensitive;
    int n;
    cin >> pattern >> sensitive >> n;

    if (!sensitive) {
        pattern = lower_copy(pattern);
    }

    for (int i = 0; i < n; i++) {
        string text;
        cin >> text;
        string target = sensitive ? text : lower_copy(text);
        if (target.find(pattern) != string::npos) {
            cout << text << '\n';
        }
    }

    return 0;
}

复杂度

设文本行和模式串长度上界为 $L$ ，共有 $n$ 行。标准库子串查找的最坏复杂度为 $O(L^2)$ ，总时间复杂度为 $O(nL^2)$ ，额外空间复杂度为 $O(L)$ 。

总结

字符串匹配题的关键是先明确比较规则，再统一输入的表示。匹配时使用规范化后的字符串，输出时使用原字符串，就能同时满足大小写选项和原行输出要求。

目录

形式化题目

思路

处理流程

代码

复杂度

总结