Don't Try to Count

原题链接：https://codeforces.com/contest/1881/problem/A

cf上的一道题，为什么发这道题呢？因为这是我打cf的第一题，今天回过头来看看这题发现这题当时写的时间复杂度好高 于是乎优化了一下代码并且好好思考了一下，结果... 很成功的将时间复杂度降了下来，简单说一下我的想法，这一题无非是对string的find()函数的使用，题目大意是要寻找一个最小的值满足s是x的子串，那么如果s的倍数是x的两倍以上不存在题意，那么永远不可能出现题意，那么代码如下

find（）的时间复杂度是O(n)!!!!!!!

find（）的时间复杂度是O(n)!!!!!!!

find（）的时间复杂度是O(n)!!!!!!!

#include<bits/stdc++.h>
using namespace std;
#define int long long
void ChiefNing()
{
    int n,m;
    cin>>n>>m;
    string x,s;
    cin>>x;
    cin>>s;//s作为子串字符出现在x中
    int ans,tmp=n;//ans记录进行的operation次数，tmp记录x的长度
    for(int i=0;;i++){
        if(tmp>=m){
            ans=i;
            break;//如果长度大于等于s的长度那么就可能出现最小的值
        }
        tmp*=2;
    }
    tmp=ans;
    while(tmp--){//用while可保证最少进行0次循环
        x+=x;
    }
    if(x.find(s)!=string::npos){
        cout<<ans<<endl;
    }
    else{
        x+=x;
        if(x.find(s)!=string::npos){
            cout<<ans+1<<endl;
        }
        else{
            cout<<-1<<endl;
        }
    }
}

signed main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--)
        ChiefNing();
    return 0;
}