Reverse String

文章目录

• • 题意：
  • 题解：
  • 代码：
  • • 第一个代码
    • 第二个思路的代码

题意：

给以你个字符串a和b，现在在字符串a上选一个位置，然后向右移动再向左移动，(可以移动为0，但是向左移动后不能再向右)，问能否构造出b

题解：

这个题我想的就是直接通过a来构造b，现枚举左端点，然后枚举右移长度，因为直到b的长度，所以也就直到左移动长度。这样直接在a中截取，看得到的是否为b，但是不知道为什么我写的re了，好像是字符太大？
我看了其他人代码，有个人写的非常妙，我们不需要正好构造出b，我们就将左端点设为起点，每次枚举向右的右端点(i)，那么一部分就是0到i，另一部分就是0~i-1，将后半部分反转拼接到第一部分上，如果b属于这个字符串就说明可以构造，这个相当于我们那个的精简版，更方便也更块

代码：

第一个代码

#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b);
typedef long long ll;
using namespace std;
//qdu打铁匠
const ll INF=0x3f3f3f3f;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
int main()
{
	int q=read();
	while(q--){
		string s;
		string t;
		cin>>s>>t;
		int n=s.length();
		int m=t.length();
		bool f=0;
		for(int i=0;i<n;i++){//左端点 
			for(int j=0;j<n-i;j++){//右移动长度 
				int k=m-j-1;//左移动长度 
				if(i+j<k)continue;
				int l1=i;
				int r = i+j;
				int l2 = r-k;
				string c=s.substr(l2,r-l2);
				reverse(c.begin(),c.end());
			//	cout<<"nowl="<<s.substr(l1,r+1-l1)<<endl;
			//	cout<<"nowr="<<c<<endl;
				
				string now=s.substr(l1,r+1-l1)+c;
			//	cout<<"now="<<now<<endl;
			//	cout<<endl;
				if(now==t)
				{
					f=1;
					break;
				}
			}
		}
		if(f)puts("YES");
		else puts("NO");
	}
}

第二个思路的代码

#include <bits/stdc++.h>
using namespace std;
int t,n;
string a,b;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		bool flag = 0;
		for (int i=0;i<a.size();i++)
		{
			string s1=a.substr(0,i+1);
			string s2=a.substr(0,i);
			reverse(s2.begin(),s2.end());
			s1+=s2;
			if(s1.find(b)!=-1)
			{
				flag=1;
				break;
			}
		}
		puts(flag ? "YES" : "NO");
	}
	return 0;
}