L - Let‘s Swap(哈希 + 规律)

2023河南省赛组队训练赛（四） - Virtual Judge (vjudge.net)

约瑟夫最近开发了一款名为Pandote的编辑软件，现在他正在测试，以确保它能正常工作，否则，他可能会被解雇!Joseph通过实现对Pandote上字符串的复制和粘贴以及反向操作开始了他的测试。更具体地说，在每一步中，如果屏幕上的字符串是S，他将按顺序进行以下操作。1. 选择长度为l(1≤l≤IS)的前缀，则S可表示为AB (IA] = 1)，注意字符串B可以为空。2. 交换这两个部分，得到字符串BA。3.反转整个字符串，得到字符串(BA)"但是，由于Pandote的功能有限，他在每一步中只能选择长度不同的前缀l1和l2。现在Joseph想知道他是否可以通过几个(可能是零)步骤将字符串S转换为T。输入输入的第一行给出了测试用例的数量T (1 <T <5 × 105)。接下来是T测试用例。对于每个测试用例，第一行包含字符串S，第二行包含字符串T。S和T都由小写拉丁字母和[S] = ITI组成。第三行包含两个整数l1和l2(1≤l1, l2≤IS1, l1 # 12)，表示每一步可以选择的前缀长度。保证所有测试用例的|S]之和不超过5 × 105。

Sample 1

Inputcopy	Outputcopy
3 ljhelloh hellohlj 2 4 thisisastr htrtsasisi 3 5 abcde bcdea 1 4	yes no yes

 题解:
我们通过枚举样例可以发现如果连续两个l1或l2操作,原字符串是不变的

(假设l1 > l2)

并且如果进行(l1,l2)

相当于把字符串向左(先l1后 l2) l1 - l2个单位

或向右移动(先l2 后l1) l1 - l2个单位

那么最终答案只可能会是

(l1,l2),l1,l2...  只在原字符串上进行向左或向右移动

l1,(l1,l2),(l1,l2)...  先进行一次l1,再同上

l2,(l1,l2),(l1,l2)...   先进行一次l2,在同上

由于我们要找循环节,所以字符串都变成二倍长度

然后哈希三种情况,看字符串T是否在三种情况中出现过

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define int long long
const int N = 4e6 + 10;
typedef pair<int, int> PII;
string s,s1,s2,c;
int n,m,a,b;
int h1[N],h2[N],h[N],p[N];
int x = 133331;
int mod = 1e9 + 7;
int res;
int get(int h[],int l,int r)
{return (h[r] - h[l-1]*p[r-l+1]%mod + mod)%mod;
} 
int check(int l,int r)
{if(get(h,l,r) == res)return 1;if(get(h1,l,r) == res)return 1;if(get(h2,l,r) == res)return 1;return 0;}
void solve() 
{cin >> s >> c >> a >> b;n = s.size();s1 = s.substr(a) + s.substr(0,a);reverse(s1.begin(),s1.end());s2 = s.substr(b) + s.substr(0,b);reverse(s2.begin(),s2.end());s = s + s;s = " " + s;s1 = s1 + s1;s1 = " " + s1;s2 = s2 + s2;s2 = " " + s2;c = " " + c;res = 0;p[0] = 1;for(int i = 1;i <= 2*n;i++){p[i] = (p[i-1]*x%mod);h[i] = (h[i-1]*x%mod + s[i])%mod;h1[i] = (h1[i-1]*x%mod + s1[i])%mod;h2[i] = (h2[i-1]*x%mod + s2[i])%mod;if(i <= n)res = (res*x%mod + c[i])%mod;}if(a < b)swap(a,b);for(int i = 1,j = 1;j <= n;j++){if(check(i,i+n - 1)){cout <<"yes\n";return  ;}i = i + n - a + b;if(i >= n + 1){i = i%(n);if(!i)i = n;}}for(int i = 1,j = 1;j <= n;j++){if(check(i,i+n - 1)){cout <<"yes\n";return  ;}i = i + a - b;if(i >= n + 1){i = i%(n);if(!i)i = n;}}cout <<"no\n";
}signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;cin >> t;
//scanf("%lld",&t);while (t--) {solve();}
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB