【例70.1】 字符串移位包含问题

解题思路

交换让a是较长串，b是较短串。所有a的循环移位都可在a+a中找到起点，因此判断b是否为a+a的子串即可；b长度≤a长度保证不会跨越过多字符。

正确性说明

任一循环移位等于a+a中从某个原串位置截取长度|a|的窗口；短串若在任一窗口中出现，就在双串中出现。反向也可选择包含该短串的长度|a|窗口。

易错点

不要要求两串等长；输出true/false小写。

复杂度

朴素查找最坏O(L²)，空间O(L)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    if (a.size() < b.size())
        swap(a, b);
    cout << ((a + a).find(b) != string::npos ? "true" : "false") << "\n";
    return 0;
}