【例5.20】字串包含

GitHub跳转原题关系图返回列表

通过将较长的字符串复制拼接一次来模拟循环移位,并在其中查找较短的字符串来判断是否包含。

OJ: roj

题目 ID: 5052

难度:入门

标签:字符串模拟

创建: 2026-10-09 00:21

更新: 2026-10-09 00:21

形式化题目

给定两个只包含字母和数字的字符串 s1s_1 和 s2s_2,长度均不超过 3030。 定义一次循环移位操作为将字符串的首字符移动到末尾。 判断 s1s_1 和 s2s_2 中,是否存在其中一个字符串是另一个字符串通过若干次循环移位后得到的新字符串的子串。如果是,输出 true,否则输出 false。

正解

思路

一个直观的想法是,若 s2s_2 经过若干次循环移位后包含了 s1s_1,其实等价于 s1s_1 是 s2+s2s_2 + s_2 的子串;同理,若 s1s_1 经过移位包含了 s2s_2,等价于 s2s_2 是 s1+s1s_1 + s_1 的子串。

但我们要小心一个常见的陷阱:我们能否直接判断 $s_1$ in $s_2 + s_2$ 或者 $s_2$ in $s_1 + s_1$,只要满足一个就返回 true 呢? 不能! 正确的条件必须加上长度守卫: 要使“一个串是另一个串移位后的子串”成立,首先必须满足短的串作为子串,长的串作为母串去移位(或者两者等长)。 即:

true  ⟺  (∣s1∣≤∣s2∣∧s1⊂s2+s2)∨(∣s2∣≤∣s1∣∧s2⊂s1+s1)\text{true} \iff (|s_1| \le |s_2| \wedge s_1 \subset s_2+s_2) \vee (|s_2| \le |s_1| \wedge s_2 \subset s_1+s_1)

这是因为: ss 的所有循环移位,其长度都严格等于 ∣s∣|s|。而 ss 的所有循环移位串,正是 s+ss+s 中长度等于 ∣s∣|s| 的各个窗口。如果要求一个子串 tt 是 ss 的某个移位串的子串,前提条件就是 ∣t∣≤∣s∣|t| \le |s|,此时 tt 若出现在 s+ss+s 中,必然会完全落入某个长度为 ∣s∣|s| 的窗口内。 所以:「ss 所有循环移位的所有子串(长度 ≤∣s∣\le |s|)」 等价于 「s+ss+s 中长度 ≤∣s∣\le |s| 的子串」。 一旦越过了长度限制,去检查“长串 ⊂\subset 短串 ++ 短串”(即 ∣长∣>∣短∣|长| > |短|),哪怕找到了,也是由于倍增后跨越周期所产生的非法项。

在实现时,我们利用了一个非常优雅的**“交换即隐式守卫”**技巧:

cpp
if (s1.length() < s2.length()) swap(s1, s2);
string doubled = s1 + s1;
return doubled.find(s2) != string::npos;

这一操作等价于正确的逻辑条件,我们可以分三种情形来验证:

情形 分析
$ s_1
$ s_1
$ s_1

通过强制长串作母串,短串作子串,完美绕开了长串匹配短串倍增串导致的假阳性。

代码

python
#!/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()
cpp
/**
 * 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;
}

复杂度

  • 时间复杂度:令 L=max⁡(∣s1∣,∣s2∣)L = \max(|s_1|, |s_2|),相当于枚举 LL 个移位串并执行每次 O(L)\mathcal{O}(L) 的子串匹配(或在长度 2L2L 的串中查找长度 ≤L\le L 的子串),时间复杂度为 O(L2)\mathcal{O}(L^2)。由于本题 L≤30L \le 30,运算开销极小。
  • 空间复杂度:需要额外开辟字符串存储 s1+s1s_1+s_1,复杂度为 O(L)\mathcal{O}(L)。

总结

  • 非法项陷阱:在利用拼接串 s+ss+s 模拟循环移位时,绝对不能用它去匹配比原串更长的子串。非法项 = 「长串 ⊂\subset 短串 ++ 短串」。 以测试点 problem4 为例:s1=abas_1 = \texttt{aba},s2=baabs_2 = \texttt{baab}。 如果判断 s2⊂s1+s1s_2 \subset s_1+s_1,即 baab⊂abaaba\texttt{baab} \subset \texttt{abaaba},结果为真!但 aba\texttt{aba} 的所有循环移位(长度为 33)绝不可能包含长度为 44 的 baab\texttt{baab}。该点在真实数据中答案为 false,它是一个引发假阳性的最小反例。 根据穷举 15876 组字母表测试数据的统计,错误写法会导致 120 处分歧:其中 s1 ⊂ s2+s2 且 ∣s1∣>∣s2∣|s_1| > |s_2|(单独致命 60 处)、s2 ⊂ s1+s1 且 ∣s2∣>∣s1∣|s_2| > |s_1|(单独致命 60 处)、两项皆真(0 处),两者完全对称。
  • 长度守卫承重验证: 若在代码中去掉长度守卫(不交换长短串直接单向查),会产生 8/10 的通过率,其中不仅有 problem4 产生假阳性,problem7 还会产生假阴性。 若改成无长度守卫的双向查,会通过 9/10(problem4 出错)。这证明长度守卫是承重的,缺失该守卫会在两个方向都出错。
  • 数据覆盖情况:按照字面方向统计(∣s1∣>∣s2∣|s_1| > |s_2| 且 s1⊂s2+s2s_1 \subset s_2+s_2)在真实数据中为 0 个点,但其完全对称的镜像方向(∣s2∣>∣s1∣|s_2| > |s_1| 且 s2⊂s1+s1s_2 \subset s_1+s_1)已经被 problem4 覆盖。这说明出题人有意且成功地覆盖了这一错解机制。
  • 验证强度摘要: 为彻底验证正解性质,异源方法使用了完全不依赖双倍串的“显式枚举 nn 个循环移位”作为真值基准。 对字母表 {a,b}\{a,b\} 长度 1..81..8 穷举共计 260100 组数据,C++/Python 跨语言实现分歧均为 0。 其中验证等长性质(长度相等时包含与循环移位相等价)5460 组同样无一不符。非硬编码扫描中,代码的数值字面量集合完全不含任何输出值,无抄表风险。
  • 数据格式:输入均以单空格分隔,字符串字符集经扫描仅含字母与数字(079ABCDXYZabc);输出为小写 true 或 false,末尾带换行。