题目描述

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

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

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

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

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

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

样例

输入样例

AABCD CDAA

输出样例

true

算法1

string的find函数

旋转字符串:将字符串的第一个字符移动到末尾形成新的字符串,称为一次旋转
如果一个字符串s1是另一个字符串s2的旋转，
那么s1可以在s2 + s2的子字符串中找到。(具体例子见代码)
根据特点运用find函数可得出答案

时间复杂度

O(n)

C++ 代码

#include <iostream>  
#include <string>  
using namespace std;  

string str; // 输入的字符串  
string c;   // 输入的子字符串  

bool check(string str, string c) {
    // 拼接 str 以生成旋转字符串的所有可能组合  
    string temp = str + str; 
    // 例如: "abc" + "abc" -> "abcabc"
    // 可在"abcabc"中找到 "abc" \ "bca" \ "cab" \ "abc"所有可能,
    // 故直接在拼接后的字符串中查找即可得出答案

    // 检查 c 是否是拼接后字符串的子字符串  
    return temp.find(c) != string::npos; // 找到返回 true，否则返回 false  
}  

int main() {
    cin >> str >> c; // 输入字符串 子串

    // 保证c为子串,str为母串
    if(c.length()>str.length()){
        swap(str,c);
    }

    cout << (check(str, c) ? "true" : "false") << endl; // 输出结果  
    return 0;  
}