思维题
题目大意
给一个字符串s,一个字符串t,问能否通过在任意位置先向右遍历s一个长度(可以为0),再向左遍历一个长度(可以为0)来得到字符串t
思路
找到所有s[i]=t[0]的i,从i开始枚举向右遍历的长度(我之前进入了一个误区,每次都是向右枚举直到s[i]和t[j]不相等为止,但是这么做可能得到的结果是NO,但是正确答案却是YES,所以需要枚举向右的长度,这样才能得到正确结果),向右遍历长度的最大值等于min(len(s)-i,len(t)),然后直接暴力遍历模拟一下即可…时间复杂度为O(s*(t^2)),感觉有点极限
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t;
string s,t1;
int main()
{
cin>>t;
while(t--)
{
cin>>s>>t1;
int flag=0;
for(int i=0;i<s.size();i++)
{
if(s[i]==t1[0])
{
for(int len=0;len<=min(s.size()-i,t1.size());len++)
{
int j=i,k=0;
while(s[j]==t1[k]&&j<=i+len&&k<t1.size())
{
j++;
k++;
}
j-=2;
while(s[j]==t1[k]&&j>=0&&k<t1.size())
{
j--;
k++;
}
if(k==t1.size())
{
flag=1;
break;
}
}
}
if(flag)
break;
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}