由题意可知母串S只能通过(l1->l2) || (l2->l1)这两种变换形式,即交替进行,且易证明这两种方式最终得到的结果一样,即若不能变换成字串T,则都不能,反之都可以。

因此我们考虑一种情况即可:我们不妨考虑先进行l2(l2>l1)操作再进行l1操作。

先进行l2操作再进行l1操作(这样连续的操作我称为w操作)我们发现其实就是将母串S的前(l2-l1)位移到S串的末尾。

比如样例eg: ljhelloh ⟶(4) ehjlholl ⟶(2) ​hellohlj

就是将S串前两位lj移到了该串的末尾:lj helloh ⟶ helloh lj

我们由这个发现可以推得一个推论:

即若S串能通过w操作变换成T串则T串一定是双倍S串的子串!

举个例子:双倍S字串:ljhellohljhelloh

T串:hellohlj

但是,这是一个必要不充分条件!!

针对样例二我们发现了一个类似的推论:

双倍S字串逆序:rtsasisihtrtsasisiht

T串:htrtsasisi

经过作者尝试对于不同的l1,l2会有不同的结果

则我们推论改为:

即若S串能通过w操作变换成T串则T串一定是双倍S串或者双倍S串逆序的子串!

但是注意:这依旧是一个必要不充分条件!!

因为还有一个决定性因素l1,l2

这样的话我们就很容易地出来一个解决该问题的思路

我们在双倍S串或者双倍S串逆序中找T串的位置

如果找不到则输出no(必要不充分条件)

如果能找到字串位置p,则我们将p%gcd(n,l2-l1) < n为串长度,其中保证l2>l1 >

如果p%gcd(n,l2-l1)==0 则说明S能到T,否则不行;

为什么要让p%gcd(n,l2-l1)呢,因为我们发现被移动的字串的下一个状态一定是n与(l2-l1)的最大公约数的倍数。证明很简单(自己模拟一下也能知道)

至此本题解决

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--)
    {
        string a,b;cin>>a>>b;
        a+=a;int n=b.size();
        int l,r;cin>>l>>r;
        if(l>r)    swap(l,r);
        if(a.find(b)==a.npos)
        {
            reverse(b.begin(),b.begin()+l);
            reverse(b.begin()+l,b.end());
        }//这一步是为了让逆序的串转换为正序的串至于为什么对b操作相信聪明的你一定知道qaq
        if(a.find(b)==a.npos)
        {
            cout<<"no"<<endl;continue;
        }
        if(a.find(b)%__gcd(n,r-l)==0)    cout<<"yes"<<endl;
        else                            cout<<"no"<<endl;
    }
    return 0;
}