语言月赛 202412 正在联系教练退赛

题意分析

给定 $n$ 个队伍名称，每个是一个字符串 $s_i$，以及一个违规字典 $t_1, t_2, ..., t_m$。如果某个队伍名 $s_i$ 包含任意一个 $t_j$ 作为子串，则该队伍为违规队伍，输出 Yes，否则输出 No。

---

解题思路

暴力判断

• 枚举每个队伍名 $s_i$。
• 枚举字典中每一个字符串 $t_j$。
• 检查 $t_j$ 是否为 $s_i$ 的子串。
• 可使用 C++ 标准库中的 find 函数：s[i].find(t[j]) != s[i].npos 判断是否包含。
• 一旦匹配成功，即可判定为违规，输出 Yes，否则输出 No。

由于数据范围较小（最多 $100 \times 100$ 次字符串匹配），可以直接采用暴力法完成。

---

实现步骤

• 输入整数 $n$，读取 $n$ 个字符串作为队伍名。
  • 因为后续要判断，所以定义一个字符串数组存储。即 string s[105]。
• 输入整数 $m$，读取 $m$ 个字符串作为违规字典。
  • 因为后续要判断，所以定义一个字符串数组存储。即 string t[105]。
• 对于每个队伍名：
• 遍历所有字典中的关键词，判断是否包含该关键词。
• 只要存在任意一个匹配，就输出 Yes，否则输出 No。

---

示例代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
string s[105] , t[105];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    cin >> m;
    for (int i = 1; i <= m; i++)
        cin >> t[i];
    for (int i = 1; i <= n; i++)
    {
        bool ok = 0; // 标记变量
        for (int j = 1; j <= m; j++)
        {
            if (s[i].find(t[j]) != s[i].npos)
            {
                ok = 1;
                break;
            }
        }
        if (ok) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

时间复杂度分析

设字符串最大长度为 $L$，队伍数为 $n$，字典词数为 $m$。

• 每次判断是否为子串，C++ 中 find 的复杂度近似为 $O(L^2)$（最坏）。
• 总体复杂度为 $O(n \cdot m \cdot L^2)$，在题目数据范围内（$n,m \leq 100$，$L \leq 100$）最多约 $10^6$ 次操作，完全可接受。

---

总结

• 本题考察字符串子串匹配的基本操作。
• 暴力遍历结合标准库函数 find 已足够应对所有数据点。

适合初学者练习字符串处理和匹配逻辑。