题目描述

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

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

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

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

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

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

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

知道题使用string类的库函数会比较简单，时间复杂度O(n^2),题目数据是小于30，够了，这题是说一个是否是另一个字符串经过若干次变换后的子串，我们并不知道那个字符串长，哪一个短，特判一下，chenk函数只想到O(n^2)的做法，如果有更优的，欢迎评论

样例

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
bool check(string a,string b)
{
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j<a.size();j++)
        {
            if(a.substr(i,j)==b)
            return true;
        }
    }
    return false;
}
void out()
{
    cout<<s1<<endl<<s2<<endl;
}
int main()
{
    bool flag=false;;
    char ch;
    cin>>s1>>s2;
    string temp;
    if(s1.size()<s2.size())
    {
        temp=s1;
        s1=s2;
        s2=temp;

    }
    int num=0;
    while(num<s1.size())
    {
        s1+=s1[0];


        s1.erase(s1.begin());


        if(check(s1,s2))
        {
            flag=true;
            break;
        }
        num++;
    }
    if(flag)puts("true");
    else puts("false");


    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla