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;
}