通过将较长的字符串复制拼接一次来模拟循环移位,并在其中查找较短的字符串来判断是否包含。
OJ: roj
题目 ID: 5052
难度:入门
标签:字符串模拟
创建: 2026-10-09 00:21
更新: 2026-10-09 00:21
形式化题目
给定两个只包含字母和数字的字符串 true,否则输出 false。
正解
思路
一个直观的想法是,若
但我们要小心一个常见的陷阱:我们能否直接判断 $s_1$ in $s_2 + s_2$ 或者 $s_2$ in $s_1 + s_1$,只要满足一个就返回 true 呢?
不能!
正确的条件必须加上长度守卫:
要使“一个串是另一个串移位后的子串”成立,首先必须满足短的串作为子串,长的串作为母串去移位(或者两者等长)。
即:
这是因为:
在实现时,我们利用了一个非常优雅的**“交换即隐式守卫”**技巧:
if (s1.length() < s2.length()) swap(s1, s2);
string doubled = s1 + s1;
return doubled.find(s2) != string::npos;这一操作等价于正确的逻辑条件,我们可以分三种情形来验证:
| 情形 | 分析 |
|---|---|
| $ | s_1 |
| $ | s_1 |
| $ | s_1 |
通过强制长串作母串,短串作子串,完美绕开了长串匹配短串倍增串导致的假阳性。
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 00:01
# update_at: 2026-10-09 00:09
import sys
def contains_after_shift(s1: str, s2: str) -> bool:
"""s1 的某个循环移位串是否包含 s2:长者作母串,倍增一次后查短串。"""
if len(s1) < len(s2):
s1, s2 = s2, s1 # 长度守卫:|s2| > |s1| 时短串绝不可能包含长串,排除假阳性
return s2 in s1 + s1 # s1 + s1 把全部 |s1| 个循环移位展开在同一条串上
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
s1 = next(data, None)
s2 = next(data, None)
if s1 is None or s2 is None: # 缺参数:安静退出,与 C++ 侧一致
return
print("true" if contains_after_shift(s1.decode(), s2.decode()) else "false")
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-09 00:01
* update_at: 2026-10-09 00:09
*/
// main.cpp:字串包含 —— 长者作母串,倍增后查找短串。
//
// 一次循环移位 = 把首字符移到末尾。字符串 X 的任一循环移位长度恒为 |X|,
// 所以 |Y| > |X| 时 Y 绝不可能是 X 某个循环移位的子串;此时只可能是
// 「短的 X 是长的 Y 移位后的子串」。于是先令 s1 = 长者(母串)、s2 = 短者(子串候选),
// 问题化为「s2 是否为 s1 某个循环移位的子串」。
//
// 而 s1 的所有循环移位串拼起来就是 s1+s1 的前 |s1|+|s1| 个字符,故
// |s2| <= |s1| 时「s2 是某个循环移位的子串」等价于「s2 是 s1+s1 的子串」。
//
// 注意不能省掉这个长度守卫、改判 (s1 ⊂ s2+s2) || (s2 ⊂ s1+s1):
// 当 |s1| < |s2| 时 s2+s2 会引入跨越周期的、比 |s2| 更长的非法子串,
// 例如 s1="aba"、s2="baab" 时 "aba" ⊂ "baab"+"baab" 成立,
// 但 |aba| > |baab| 中任何一个长度为 3 的移位串,正确答案是 false(见 problem4)。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
// 判定「s1 经过若干次循环移位后,是否包含 s2」;调用前不要求 |s1| >= |s2|。
bool contains_after_shift(string s1, string s2) {
if (s1.length() < s2.length()) {
swap(s1, s2); // 长度守卫:长者作母串,短者作子串候选
}
string doubled = s1 + s1; // 环形展开,一次枚举 s1 的全部循环移位
return doubled.find(s2) != string::npos;
}
void solve() {
string s1, s2;
if (!(cin >> s1 >> s2)) return; // 无输入或缺参数:安静退出
if (contains_after_shift(s1, s2)) {
cout << "true\n";
} else {
cout << "false\n";
}
}
int main() {
solve();
return 0;
}复杂度
- 时间复杂度:令
,相当于枚举 个移位串并执行每次 的子串匹配(或在长度 的串中查找长度 的子串),时间复杂度为 。由于本题 ,运算开销极小。 - 空间复杂度:需要额外开辟字符串存储
,复杂度为 。
总结
- 非法项陷阱:在利用拼接串
模拟循环移位时,绝对不能用它去匹配比原串更长的子串。非法项 = 「长串 短串 短串」。 以测试点 problem4为例:, 。 如果判断 ,即 ,结果为真!但 的所有循环移位(长度为 )绝不可能包含长度为 的 。该点在真实数据中答案为 false,它是一个引发假阳性的最小反例。 根据穷举 15876 组字母表测试数据的统计,错误写法会导致 120 处分歧:其中s1 ⊂ s2+s2且(单独致命 60 处)、 s2 ⊂ s1+s1且(单独致命 60 处)、两项皆真(0 处),两者完全对称。 - 长度守卫承重验证:
若在代码中去掉长度守卫(不交换长短串直接单向查),会产生 8/10 的通过率,其中不仅有
problem4产生假阳性,problem7还会产生假阴性。 若改成无长度守卫的双向查,会通过 9/10(problem4出错)。这证明长度守卫是承重的,缺失该守卫会在两个方向都出错。 - 数据覆盖情况:按照字面方向统计(
且 )在真实数据中为 0 个点,但其完全对称的镜像方向( 且 )已经被 problem4覆盖。这说明出题人有意且成功地覆盖了这一错解机制。 - 验证强度摘要:
为彻底验证正解性质,异源方法使用了完全不依赖双倍串的“显式枚举
个循环移位”作为真值基准。 对字母表 长度 穷举共计 260100 组数据,C++/Python 跨语言实现分歧均为 0。 其中验证等长性质(长度相等时包含与循环移位相等价)5460 组同样无一不符。非硬编码扫描中,代码的数值字面量集合完全不含任何输出值,无抄表风险。 - 数据格式:输入均以单空格分隔,字符串字符集经扫描仅含字母与数字(
079ABCDXYZabc);输出为小写true或false,末尾带换行。