题目描述

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串 s1
和 s2
，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。

例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串，而 ABCD 与 ACBD 则不能通过多次移位来得到其中一个字符串是新串的子串。

输入格式
共一行，包含两个字符串，中间由单个空格隔开。

字符串只包含字母和数字，长度不超过 30
。

输出格式
如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串，则输出 true，否则输出 false。

输入样例：
AABCD CDAA
输出样例：
true

样例

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

int main(){
    string a, b;
    cin >> a >> b;
    if(a.size() < b.size()) swap(a, b);
    for(int i = 0; i < a.size() ; i++){
        a = a.substr(1) + a[0];
        for(int j = 0; j + b.size() <= a.size(); j++){
            string str = a.substr(j, b.size()); //获得每个循环字符串中长度和b一样的字符串
            cout << str << endl; 
            if(str == b){
                cout << "true";
                return 0;
            }
        }
    }
    cout << "false";
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla