P8892 「UOI-R1」磁铁 题解
yeshubo_qwq
2022-12-10 21:10:13
## Solution
操作 $2$ 使得磁铁 $a$ 本质为环，结合操作 $1$，可以删除任意位置的字符。
破环为链，以每个位置为起点进行判定，使用双指针可以做到 $O(n^2)$（$n$ 为磁铁长度）。
## Code
```cpp
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int T,n,m,i,l,r,sum;
string s,t;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>T;
while (T--){
cin>>s>>t;
n=s.size(),s=" "+s+s;
m=t.size(),t=" "+t;
if (n<m){
cout<<"N\n";
continue;
}
for (i=1;i<=n;i++){
l=i,r=1,sum=0;
while (l<=i+n-1 && r<=m)
if (s[l]==t[r]) l++,r++,sum++;
else l++;
if (sum==m) break;
}
cout<<(i>n?"N\n":"Y\n");
}
return 0;
}
```