読者です 読者をやめる 読者になる 読者になる

日々精進

aikoと旅行とプログラミング

【AOJ 2727】M and A

問題

M and A | Aizu Online Judge

方針

  • SとTの部分文字列を交互に繋げてSを作ることができるか調べる.
  • Sの部分文字列は自明にSに含まれているので, Tの部分文字列を考える.
  • Tの先頭から順に探索し, 部分文字列であるかを試す. (Sの偶数番目と奇数番目をとった場合の2通り)

コード

#include<iostream>

using namespace std;

string S, T, s, t;

bool check(){
  int i;
  int pos = 0;

  if(s == "") return true;
  
  for(i = 0 ; i < (int)T.size() ; i++){
    while(T[i]!=s[pos] && i < (int)T.size()) i++;
    if(i >= (int)T.size()) break;
    pos++;
    if(pos == (int)s.size()){
      return true;
    }
  }

  return false;
}

signed main(){
  bool flag = false;
  cin >> S >> T;
  
  s = "";
  for(int i = 0 ; i < (int)S.size() ; i+=2) s += S[i];
  flag |= check();

  s = "";
  for(int i = 1 ;  i < (int)S.size() ; i+=2) s += S[i];
  flag |= check();

  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}