题目描述
其实这里就是移位然后看小串是否在大串中,这里我之前的做法是找不到的话就移位,但是我发现可以直接将大串翻倍就好了,这样直接搜两遍,注重效率的话直接就是将2*j-1替换成j+k就好了
样例
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main()
{
string a,b;
cin >> a >> b;
int i,j,k,m,t;
k=j=a.size(); //k大值,j小
if(j>b.size())
j=b.size();
else k=b.size();
if(a.size()<b.size())
swap(a,b);
a +=a;
for(t=0;t<k;t++)
{
m=0;
int tmp=t;
for(i=0;i<j*2-1;i++)
if(a[i]==b[tmp])
m++,tmp++;
if(m==j)
break;
//a=a.back()+a.substr(0,a.size()-1);
}
if(m==j)puts("true");
else puts("false");
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla