AtCoder|ABC054:B - Template Matching

AtCoderの過去問対策です。ABCで解けなかった問題、ためになった問題のコードを備忘録として残します。

問題

B - Template Matching

解説

https://img.atcoder.jp/abc054/editorial.pdf

解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N, M; cin >> N >> M;
  vector<string> A(N);
  vector<string> B(M);
  for(int i = 0; i < N; i++){
    cin >> A.at(i);
  }
  for(int i = 0; i < M; i++){
    cin >> B.at(i);
  }
  
  for(int i = 0; i <= N-M; i++){
    for(int j = 0; j <= N-M; j++){
      bool isContain = true;
      for(int k = 0; k < M; k++){
        for(int l = 0; l < M; l++){
          if(A.at(i+k).at(j+l) != B.at(k).at(l)){
            isContain = false;
            break;
          }
        }
        if(!isContain){
          break;
        }
      }
      if(isContain){
        cout << "Yes\n";
        return 0;
      }
    }
  }
  cout << "No\n";
}

出力の処理を変更↓

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N, M; cin >> N >> M;
  vector<string> A(N);
  vector<string> B(M);
  for(int i = 0; i < N; i++) cin >> A.at(i);
  for(int i = 0; i < M; i++) cin >> B.at(i);
  
  bool exist = false;
  for(int i = 0; i <= N-M; i++){
    for(int j = 0; j <= N-M; j++){
      bool match = true;
      for(int k = 0; k < M; k++){
        for(int l = 0; l < M; l++){
          if(A.at(i+k).at(j+l) != B.at(k).at(l)){
            match = false;
          }
        }
      }
      if(match) exist = true;
    }
  }
  if(exist) cout << "Yes\n";
  else cout << "No\n";
}