[NOIP2011-普及] 统计单词数

题目描述

给定一个只含字母的单词和一篇只含字母与空格的文章，输出该单词在文章中出现次数及首次出现位置（首字母下标从 $0$ 开始）。匹配不区分大小写，但必须是独立单词，不能是其他单词的一部分。若未出现则输出 $-1$ 。

数据范围：单词长度 $1 \sim 10$ ，文章长度 $1 \sim 10^6$ 。

思路

先把单词和文章统一转成小写，再枚举文章中的每个起始位置，检查该位置起连续 $|w|$ 个字符是否与单词相等，并确认左右两侧不是字母（即处于空格或端点）。记录匹配次数和第一次匹配的位置即可。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-02 09:15
# update_at: 2026-10-02 09:15

import re
import sys
from collections.abc import Iterator


def find_hits(article: str, word: str) -> Iterator[int]:
    """产出 word 作为独立单词在 article 中每次匹配的起始下标（不区分大小写）。

    文章只含字母和空格，所以单词边界等价于"前后不是小写字母"；
    两侧的环视让整串匹配只需一次线性扫描，不产生重叠假匹配。
    """
    pattern = re.compile(rf'(?<![a-z]){re.escape(word)}(?![a-z])')
    return (m.start() for m in pattern.finditer(article))


def solve() -> None:
    data = iter(sys.stdin.read().splitlines())  # 文章里的空格是单词边界，必须按行保留
    word = next(data).strip().lower()
    article = next(data).lower()

    hits = list(find_hits(article, word))
    if hits:
        print(len(hits), hits[0])  # 出现次数 + 首次位置（首字母下标，从 0 计）
    else:
        print(-1)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * 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-10-06 14:33
 * update_at: 2026-10-06 14:33
 */

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

typedef long long ll;

string word, article;

// 把 c 转成小写
inline char lower(char c) {
    if (c >= 'A' && c <= 'Z') return c - 'A' + 'a';
    return c;
}

// 判断 c 是否为字母
inline bool is_alpha(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

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

    getline(cin, word);
    getline(cin, article);

    // 统一转小写
    for (size_t i = 0; i < word.size(); ++i) word[i] = lower(word[i]);
    for (size_t i = 0; i < article.size(); ++i) article[i] = lower(article[i]);

    ll m = word.size();
    ll n = article.size();
    ll cnt = 0;
    ll first = -1;

    // 在 article 中逐位检查是否匹配 word 且左右为单词边界
    for (ll i = 0; i + m <= n; ++i) {
        // 检查 article[i..i+m-1] 是否等于 word
        bool match = true;
        for (ll j = 0; j < m; ++j) {
            if (article[i + j] != word[j]) {
                match = false;
                break;
            }
        }
        if (!match) continue;

        // 左边界：i == 0 或 article[i-1] 不是字母
        if (i > 0 && is_alpha(article[i - 1])) continue;
        // 右边界：i + m == n 或 article[i+m] 不是字母
        if (i + m < n && is_alpha(article[i + m])) continue;

        ++cnt;
        if (first == -1) first = i;
    }

    if (cnt == 0) {
        cout << -1 << '\n';
    } else {
        cout << cnt << ' ' << first << '\n';
    }
    return 0;
}

[NOIP2011-普及] 统计单词数

目录

题目描述

思路

参考代码