Codeforces 550A Two Substrings

知识点:字符串、循环、STL

题目

You are given string s. Your task is to determine if the given string s contains two non-overlapping substrings “AB” and “BA” (the substrings can go in any order).

输入

The only line of input contains a string s of length between 1 and 105 consisting of uppercase Latin letters.

输出

Print “YES” (without the quotes), if string s contains two non-overlapping substrings “AB” and “BA”, and “NO” otherwise.

样例

输入1

ABA

输出1

NO

输入2

BACFAB

输出2

YES

输入3

AXBYBXA

输出3

NO

提示

In the first sample test, despite the fact that there are substrings “AB” and “BA”, their occurrences overlap, so the answer is “NO”.
In the second sample test there are the following occurrences of the substrings: BACFAB.
In the third sample test there is no substring “AB” nor substring “BA”.

题意

判断字符串中是否同时存在不重叠字串“AB”和“BA”

思路(罚自己写一题多解)

一、

存在性问题,考虑AB和BA是否都出现过一次,讨论AB在前和BA在前两种情况

代码

//克服WA难,终得AC
#include"bits/stdc++.h"
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define reb(i,a,b) for(ll i=a;i<=b;i++)
#define rev(i,a,b) for(ll i=a-1;i>=b;i--)
#define red(i,a,b) for(ll i=a;i>=b;i--)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=2e6+10;

string str;

int main() {
   
  cin>>str;
  ll p=str.find("AB"),q=str.find("BA");
  if(p!=str.npos&&str.find("BA",p+2)!=str.npos||q!=str.npos&&str.find("AB",q+2)!=str.npos)
    cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

  return 0;
}

二、

不讨论AB出现顺序,AB,BA相连时可能会出现ABA,BAB子串,用乱码覆盖掉这些子串后的字符串AB,BA不相连,而ABA,BAB可提供AB或BA子串,覆盖后的AB,BA同时存在、一个(AB或BA)和(ABA或BAB)同时存在、ABA或BAB出现两次及以上都能判断答案是YES。
这个思路笔者调不出AC代码,希望网友能分享见解。
(看来连罚自己写一题多解的能力都没有……)

代码(Runtime error on test 19)

//克服WA难,终得AC
#include"bits/stdc++.h"
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define reb(i,a,b) for(ll i=a;i<=b;i++)
#define rev(i,a,b) for(ll i=a-1;i>=b;i--)
#define red(i,a,b) for(ll i=a;i>=b;i--)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

string str;

int main() {
   
  cin>>str;
  ll cnt=0;
  bool ab,ba;
  rep(i,0,str.length()-2)
  if(str.substr(i,3)=="ABA"||str.substr(i,3)=="BAB") {
   
    cnt++;
    str.replace(i,3,"###");
  }
  ab=str.find("AB")!=str.npos;
  ba=str.find("BA")!=str.npos;
  if(ab&&ba||ab&&cnt||ba&&cnt||cnt>1)  cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

  return 0;
}
全部评论

相关推荐

这是什么操作什么意思,这公司我服了...
斯派克spark:意思是有比你更便宜的牛马了
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
吴offer选手:HR:我KPI到手了就行,合不合适关我什么事
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务