由题意可知母串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;
}