B4435 [语言月赛 202511] 太空曼波

· · 题解

来源

2025 年 11 月语言月赛，由洛谷网校提供。

考察字符串。

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

文字题解

本题的要求非常明确，首先，我们枚举 s_i；再将 s_i 分为前缀 p_i 和后缀 q_i，并尝试将 p_i 与其他串的前缀匹配，后缀 q_i 与其他串的后缀匹配。

难点在于：如何拆分，如何匹配。

:::info[string: substr]{open} string 类型是 C++ STL 提供的字符串模板类。其中，成员函数 substr 用于提取子串。

substr 函数需要传入两个参数，第一个参数为子串开始的下标，第二个参数为需要截取的子串长度。如果从该下标开始到字符串结束，没有这么长的子串，则在字符串末尾截断，不会出现运行时错误。

下面是一个使用示例。

string s = "abcd1234";
cout << s.substr(0, 4) << endl; // abcd
cout << s.substr(2, 3) << endl; // cd1
cout << s.substr(6, 8) << endl; // 34

:::

使用 substr 函数，我们可以很方便的对字符串 s_i 进行拆分。枚举 p_i 的长度 l，则 q_i 的长度为 |s_i|-l。需要注意的是，题目不允许 p_i,q_i 为空串，因此 l 的枚举范围应该是 1\sim |s_i|-1。

通过 substr 函数，我们可以提取 p_i,q_i。

string p = s[i].substr(0, l);
string q = s[i].substr(l, (int)s[i].size() - l);

之后，我们分别枚举，对 p_i,q_i 寻找匹配的串。

对于 p_i，我们枚举 j，需要提取 s_j 中与 p_i 相同长度的前缀，并比较它们是否相同。我们首先需要保证这个长度的前缀存在，即，需要首先比较 |p_i| 与 |s_j| 的大小，如果 |s_j|<|p_i|，直接跳过即可。否则，我们同样使用 substr 提取前缀。