语言月赛 202401 Genshin 玩家

题意分析

给定一个字符串 $s$，要求统计有多少组满足以下条件的子串组合：

• 子串 $s[l_1, r_1] = \text{Genshin}$；
• 子串 $s[l_2, r_2] = \text{player}$；
• 满足区间位置条件：$1 \le l_1 \le r_1 < l_2 \le r_2 \le |s|$。

每对满足条件的子串组合算作一个方案，输出总方案数。

---

解题思路

本题目标是统计所有满足：

• $s[l_1, r_1] = \text{Genshin}$；
• $s[l_2, r_2] = \text{player}$；
• 并且 $r_1 < l_2$；

的合法组合数量。

简单暴力枚举法

• Genshin 长度为 7，player 长度为 6。
• 从字符串中枚举所有可能的 $l_1$ 和 $l_2$，判断从 $l_1$ 开始的 7 个字符是否为 Genshin，从 $l_2$ 开始的 6 个字符是否为 player，并判断是否满足 $l_1 + 6 < l_2$（即 $r_1 < l_2$）。

该方法虽然暴力，但思路直观、易于实现，也能通过数据范围较小的情况（$n \le 2000$）。

---

实现步骤

1. 初始化答案计数器 ans = 0。
2. 遍历所有可能的 $l_1$（从 $0$ 到 $n - 7$）：
3. 若 s.substr(l1, 7) == "Genshin"：
   • 遍历所有可能的 $l_2$（从 $l_1 + 7$ 到 $n - 6$）：
   • 若 s.substr(l2, 6) == "player"：
     • 满足条件，ans += 1。
4. 输出 ans。

---

时间复杂度分析

• 外层枚举 $l_1$ 有 $O(n)$ 次；
• 每次内层枚举 $l_2$ 最多 $O(n)$ 次；
• 子串比较为 $O(1)$（因为长度固定）；
• 整体时间复杂度为 $O(n^2)$，适用于 $n \le 2000$ 的限制。

---

总结

• 本题可用简单双重循环暴力枚举所有合法组合；
• 关键在于通过 substr 判断固定长度的目标串；
• 不需要额外空间，仅使用原始字符串本身进行位置匹配；
• 思路朴素直观，是入门字符串匹配题目的良好练习案例。