Submission #1591066


Source Code Expand

// テンプレートマッチング

#include <bits/stdc++.h>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

bool check(const vector<string> &va, const vector<string> &vb, int x, int y) {
  bool result = true;
  REP(ty, vb.size()) {
    REP(tx, vb[0].size()) {
      if(vb[ty][tx] != va[y+ty][x+tx]) {
        result = false;
        break;
      }
    }
  }
  return result;
}

void printall(vector<string> &vs) {
  REP(ty, vs.size()) {
    REP(tx, vs[0].size()) {
      cout << vs[ty][tx];
    }
    cout << endl;
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> va(n);
  vector<string> vb(m);
  REP(i, n) {
    cin >> va[i];
  }
  REP(i, m) {
    cin >> vb[i];
  }
  /*
  printall(va);
  cout << endl;
  printall(vb);
  */

  REP(ty, va.size() - vb.size() + 1) {
    REP(tx, va[0].size() - vb[0].size() + 1) {
      bool result = check(va, vb, tx, ty);
      eprintf("check x,y,r:%d,%d,%d\n", tx, ty, result);
      if(result) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;

  return 0;
}

Submission Info

Submission Time
Task B - Template Matching
User yoshi_k
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1353 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 200 / 200
Status
AC × 2
AC × 10
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB