题目描述
我们需要编写一个程序来审查一段文本，检查其中是否包含某些指定的“违禁词”。
-
输入：
- 一个整数
N，表示违禁词的数量。 - 接下来
N行，每行一个违禁词（由大小写字母、数字、空格、ASCII标点组成，长度不超过10）。 - 一个非负整数
k，作为警告阈值。 - 最后一行是待审查的文本（长度不超过5000，包含大小写字母、数字、空格、ASCII标点）。
- 一个整数
-
处理规则：
- 统计文本中出现违禁词的总次数。
- 核心规则： 从左到右处理文本，违禁词按照输入顺序依次处理。对于重叠的情况，无论计数还是替换，查找完成后从违禁词末尾继续处理。 (注意：这里的描述与代码实现可能略有出入，我们将重点分析代码的实现方式)。
-
输出：
- 如果违禁词总次数
cnt小于阈值k：输出替换后的文本，其中所有找到的违禁词都被替换为<censored>。 - 如果违禁词总次数
cnt大于等于阈值k：先输出一行cnt（违禁词总数），然后输出一行He Xie Ni Quan Jia!。
- 如果违禁词总次数
样例
输入样例1:
5
MaoNiang
SeQing
BaoLi
WeiGui
BuHeShi
4
BianCheng MaoNiang ba! WeiGui De Hua Ye Keyi Shuo! BuYao BaoLi NeiRong.
输出样例1:
BianCheng <censored> ba! <censored> De Hua Ye Keyi Shuo! BuYao <censored> NeiRong.
(解释：找到了 MaoNiang, WeiGui, BaoLi 共 3 个违禁词。3 < 4，所以替换输出。)
输入样例2:
5
MaoNiang
SeQing
BaoLi
WeiGui
BuHeShi
3
BianCheng MaoNiang ba! WeiGui De Hua Ye Keyi Shuo! BuYao BaoLi NeiRong.
输出样例2:
3
He Xie Ni Quan Jia!
(解释：找到了 3 个违禁词。3 >= 3，所以输出数量和警告。)
输入样例3:
2
AA
BB
3
AAABBB
输出样例3:
<censored>A<censored>B
(解释：代码会先找 AA，找到第一个 AA 并标记。然后继续找 AA，没找到。再找 BB，找到第一个 BB 并标记。总共找到 2 个。2 < 3，所以替换输出。)
输入样例4:
2
AB
BB
3
AAABBB
输出样例4:
AA<censored><censored>
(解释：代码先找 AB，找到 AAABBB 中的 AB 并标记。然后继续找 AB，没找到。再找 BB，找到 AAABBB 中的 BB 并标记。总共找到 2 个。2 < 3，所以替换输出。)
输入样例5:
2
BB
AB
3
AAABBB
输出样例5:
AAA<censored>B
(解释：代码先找 BB，找到 AAABBB 中的 BB 并标记。然后继续找 BB，没找到。再找 AB，找到 AAABBB 中的 AB 并标记。总共找到 2 个。2 < 3，所以替换输出。注意这里与样例4的区别在于查找顺序不同，导致标记/替换的位置不同。)
算法分析
(基于字符串查找和替换的模拟)
代码的核心思路是：
1. 读取所有输入：违禁词列表 a，阈值 k，待检查文本 s。
2. 初始化违禁词计数器 cnt = 0。
3. 遍历每一个违禁词 a[i] (从输入的第一个到最后一个)。
4. 对于当前的违禁词 a[i]，遍历文本 s 的所有可能起始位置 j。
5. 在位置 j 检查文本 s 中从 j 开始、长度为 a[i].size() 的子串是否完全等于 a[i]。
6. 如果找到匹配：
* 将计数器 cnt 加 1。
* 关键操作： 使用 s.replace(j, len, string(1, 1)) 将文本 s 中匹配到的违禁词（从 j 开始，长度为 len）替换为一个特殊的、单一的标记字符 (ASCII码为 1 的字符，通常是不可打印字符，选择它是因为它极不可能出现在原始输入文本中)。这样做是为了：
* 标记这个位置已经被一个违禁词占据。
* 防止这个被替换掉的部分再次被后续的查找（无论是查找同一个违禁词还是其他违禁词）匹配到。 例如，如果违禁词是 “catcat” 和 “cat”，文本是 “catcat”，先找到 “catcat” 并替换后，就不会再找到里面的 “cat” 了。如果先找 “cat”，找到第一个 “cat” 并替换后，也不会影响第二个 “cat”（如果存在且未被覆盖）或者包含它的 “catcat” 的查找（如果查找顺序不同）。
* 注意: 这个替换操作会改变字符串 s 的内容和可能改变其长度（因为是用一个字符替换了len个字符）。内层循环 for (int j = ...) 会继续从 j+1 开始检查，这意味着它并没有严格遵循题目描述中“从违禁词末尾继续处理”的规则（即跳过 len 个字符）。但通过原地替换，它间接实现了类似的效果——被替换的部分不会再参与匹配。
7. 所有违禁词都检查完毕后，比较 cnt 和 k。
8. 如果 cnt < k: 遍历修改后的字符串 s。遇到普通字符直接输出；遇到之前插入的特殊标记字符 (char)1，则输出替换文本 <censored>。
9. 如果 cnt >= k: 输出计数 cnt 和警告信息 He Xie Ni Quan Jia!。
代码实现细节解释：
#include <bits/stdc++.h>: 包含了 C++ 标准库的大部分头文件，方便使用vector,string,cin,cout,getline,replace,substr等。using namespace std;: 避免每次使用标准库内容时写std::。using i64 = long long;: 定义i64作为long long的别名（虽然在这个题目中没用到）。ios::sync_with_stdio(false); cin.tie(nullptr);: 用于加速 C++ 的输入输出流，在处理大量输入输出时有用。vector<string> a(n);: 定义一个动态数组（向量）a来存储n个违禁词。cin.ignore();: 在读取整数k之后，cin会留下一个换行符在缓冲区。getline读取整行时会读到这个换行符导致读入空字符串。cin.ignore()会读取并丢弃这个换行符，确保getline能正确读到下一行的文本。string s; getline(cin, s);: 读取包含空格的整行文本到字符串s。int len = a[i].size();: 获取当前违禁词a[i]的长度。(int)s.size(): 将s.size()（通常是size_t类型）转换为int，以避免与j + len比较时可能出现的类型警告或问题。s.substr(j, len): 获取s中从索引j开始，长度为len的子字符串。s.replace(j, len, string(1, 1)): 将s中从索引j开始的len个字符替换为string(1, 1)。string(1, 1)创建一个包含 1 个字符、该字符 ASCII 码为 1 的字符串。if (s[i] == 1): 在最后输出时，检查当前字符是否是那个特殊的标记字符 (ASCII 码为 1)。
关于重叠处理方式的再讨论：
代码的实现方式是通过原地修改字符串并使用特殊标记字符来处理重叠和计数。它按违禁词列表的顺序处理，对每个违禁词，从头到尾扫描文本查找所有出现。一旦找到并替换，被替换的部分就不会再被匹配。这与严格的“单次遍历文本，遇到任何违禁词就处理并跳过”有所不同，但在许多情况下能得到相似或正确的结果，特别是当违禁词之间没有复杂的重叠，或者当替换标记能有效阻止后续匹配时。例如，样例 4 和 5 的结果差异就体现了处理顺序和替换策略的影响。
时间复杂度
- 读取输入： O(N * L_avg + S)，其中 L_avg 是违禁词平均长度，S 是文本长度。
- 核心处理循环：
- 外层循环
N次 (遍历违禁词)。 - 内层循环最多
S次 (遍历文本位置)。 - 循环内部：
s.substr(j, len): 时间复杂度与子串长度len成正比，O(L)。s.replace(j, len, replacement): 在std::string中，替换操作可能需要移动后续字符，最坏情况下时间复杂度可能是 O(S)。但在许多实现和场景下，如果替换长度较小或使用特定优化（如 COW - Copy-On-Write，虽然 C++11 后不保证），可能更接近 O(L + S_remaining)。为保守估计，可以认为是 O(S)。
- 因此，总时间复杂度大致为 O(N * S * (L + S)) 或更宽松地 O(N * S^2)。
- 考虑到
L <= 10远小于S <= 5000，如果replace操作近似 O(S)，则复杂度较高。但如果substr和replace内部实现效率较高（例如substrO(L)，replace平均 O(L + S_moved)），则可能接近 O(N * S * L)。对于 S=5000, N=100, L=10，O(NSL) = 100 * 5000 * 10 = 5 * 10^6，这是可以在几百毫秒内完成的。O(NS^2) = 100 * 5000^2 = 2.5 * 10^9 则太慢。因此，std::string的操作效率很关键，通常它们比 O(S) 要好，特别是substr。replace的效率依赖于具体实现和替换内容。鉴于题目时间限制，O(NS*L) 应该是可以通过的复杂度级别。
- 外层循环
- 输出： O(S’)，其中 S’ 是替换后字符串的长度（可能小于 S）。
综合来看，主要复杂度在核心处理循环，估计为 O(N * S * L) 或略高，在给定限制下是可接受的。
空间复杂度
- 存储违禁词：O(N * L_avg)。
- 存储文本：O(S)。
- 总空间复杂度：O(N * L_avg + S)。
C++ 代码
#include <bits/stdc++.h> // 引入所有标准库头文件
using namespace std; // 使用 std 命名空间
using i64 = long long; // 定义 i64 为 long long 的别名（本题未使用）
int main() {
// 优化 C++ 输入输出流速度
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; // 违禁词数量
cin >> n; // 读取 N
vector<string> a(n); // 创建一个大小为 n 的字符串向量（动态数组）来存储违禁词
for (int i = 0; i < n; i ++ ) {
cin >> a[i]; // 循环读取 n 个违禁词
}
int k; // 警告阈值
cin >> k; // 读取 k
cin.ignore(); // 忽略掉 cin 读取 k 后留下的换行符，防止影响 getline
string s; // 用于存储待检查的文本
getline(cin, s); // 读取一整行文本（包含空格）
int cnt = 0; // 初始化违禁词计数器
// 外层循环：遍历输入的每一个违禁词
for (int i = 0; i < n; i ++ ) {
int len = a[i].size(); // 获取当前违禁词 a[i] 的长度
// 内层循环：遍历文本 s 的所有可能的起始位置 j
// 条件 j + len <= (int)s.size() 确保子串不会越界
for (int j = 0; j + len <= (int)s.size(); j ++ ) {
// 检查从位置 j 开始，长度为 len 的子串是否等于当前违禁词 a[i]
if (s.substr(j, len) == a[i]) {
// 如果匹配成功：
// 1. 将文本 s 中从 j 开始的 len 个字符替换为单个特殊字符 (ASCII 1)
// 使用 string(1, 1) 创建一个包含一个 ASCII 码为 1 的字符的字符串
// 这个替换操作会修改 s，并可能改变其长度
s.replace(j, len, string(1, 1));
// 2. 违禁词计数器加 1
cnt ++ ;
// 注意：这里没有根据题目描述的“从违禁词末尾继续处理”来调整 j
// 但因为 s 被修改了，被替换的部分不会再被匹配到，间接处理了重叠
}
}
}
// 判断计数值 cnt 是否小于阈值 k
if (cnt < k) {
// 如果小于阈值，输出替换后的文本
for (int i = 0; i < s.size(); i ++ ) {
// 遍历修改后的字符串 s
if (s[i] == 1) {
// 如果当前字符是之前替换用的特殊标记字符 (ASCII 1)
cout << "<censored>"; // 输出替换文本
} else {
// 否则，是普通字符
cout << s[i]; // 直接输出该字符
}
}
cout << "\n"; // 输出换行符
} else {
// 如果大于等于阈值
cout << cnt << "\nHe Xie Ni Quan Jia!\n"; // 输出违禁词总数和警告信息
}
return 0; // 程序正常结束
}
