专栏文章

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

览览遍千秋七海
B4435题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1ud6z
此快照首次捕获于
2025/12/01 19:11
3 个月前
此快照最后确认于
2025/12/01 19:11
3 个月前
查看原文

来源

2025 年 11 月语言月赛，由洛谷网校提供。
考察字符串。

文字题解

本题的要求非常明确，首先，我们枚举 sis_i；再将 sis_i 分为前缀 pip_i 和后缀 qiq_i，并尝试将 pip_i 与其他串的前缀匹配，后缀 qiq_i 与其他串的后缀匹配。
难点在于：如何拆分，如何匹配。
string: substr
string 类型是 C++ STL 提供的字符串模板类。其中，成员函数 substr 用于提取子串。
substr 函数需要传入两个参数，第一个参数为子串开始的下标，第二个参数为需要截取的子串长度。如果从该下标开始到字符串结束，没有这么长的子串，则在字符串末尾截断，不会出现运行时错误。
下面是一个使用示例。
CPP
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 函数，我们可以很方便的对字符串 sis_i 进行拆分。枚举 pip_i 的长度 ll，则 qiq_i 的长度为 ∣si∣−l|s_i|-l。需要注意的是，题目不允许 pi,qip_i,q_i 为空串，因此 ll 的枚举范围应该是 1∼∣si∣−11\sim |s_i|-1。
通过 substr 函数，我们可以提取 pi,qip_i,q_i。
CPP
string p = s[i].substr(0, l);
string q = s[i].substr(l, (int)s[i].size() - l);
之后，我们分别枚举，对 pi,qip_i,q_i 寻找匹配的串。
对于 pip_i，我们枚举 jj，需要提取 sjs_j 中与 pip_i 相同长度的前缀，并比较它们是否相同。我们首先需要保证这个长度的前缀存在，即，需要首先比较 ∣pi∣|p_i| 与 ∣sj∣|s_j| 的大小，如果 ∣sj∣<∣pi∣|s_j|<|p_i|，直接跳过即可。否则，我们同样使用 substr 提取前缀。
qiq_i 与 pip_i 同理，只不过提取的内容从前缀变为后缀。前缀提取的开始下标为 00，长度为 ∣pi∣|p_i|；后缀提取的开始下标为 ∣sk∣−∣qi∣|s_k|-|q_i|，长度为 ∣qi∣|q_i|。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...