아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

빅 픽쳐

시간 제한2초메모리 제한512 MB

요약
주어진 그림이 대작 안에서 회전 없이 정확히 일치하는 왼쪽 위 위치 개수를 셉니다.
난이도

보통10점 중 7점

유형
문자열 매칭
정답자
아직 제출이 없습니다

문제

재혁이는 화가지만 돈이 없어서 새 그림을 그릴 화판조차 없다. 그래서 아직 팔리지 않은 그림을 꿰매 이어 붙여 커다란 그림 한 장을 만들기로 했고, 꼬박 하루를 매달린 끝에 걸작 한 점을 완성했다.

어느 날 재혁이는 아직 팔리지 않았던 그림 한 장을 사겠다는 전화를 받았다. 그런데 걸작을 만들 때 어떤 그림을 썼는지 기록해 두지 않아서, 그 그림이 걸작의 어느 자리에 들어갔는지 직접 찾아야 한다.

흑백으로 표현한 그림 한 장과 걸작이 주어진다. 그림이 걸작 안에 나타나는 위치가 몇 군데인지 세어라. 그림은 붙인 모양 그대로이므로 돌리거나 뒤집지 않으며, 그림의 모든 칸이 걸작의 같은 자리 칸과 일치하는 왼쪽 위 좌표를 한 위치로 센다. 위치끼리 겹쳐도 각각 센다.

입력

첫째 줄에 정수 hph_p, wpw_p, hmh_m, wmw_m이 공백으로 구분되어 주어진다. 차례대로 사용한 그림의 높이와 너비, 걸작의 높이와 너비다.

다음 hph_p개의 줄에 사용한 그림이 한 줄에 wpw_p글자씩 주어지고, 이어지는 hmh_m개의 줄에 걸작이 한 줄에 wmw_m글자씩 주어진다. 두 그림 모두 문자 'o'와 'x'로만 이루어져 있다.

1≤hp≤hm≤20001 \le h_p \le h_m \le 2000, 1≤wp≤wm≤20001 \le w_p \le w_m \le 2000이다.

출력

사용한 그림이 걸작에 나타나는 위치의 개수를 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    4 4 10 10
    oxxo
    xoox
    xoox
    oxxo
    xxxxxxoxxo
    oxxoooxoox
    xooxxxxoox
    xooxxxoxxo
    oxxoxxxxxx
    ooooxxxxxx
    xxxoxxoxxo
    oooxooxoox
    oooxooxoox
    xxxoxxoxxo
    
    예상 출력
    4
    
  2. 예제 2

    입력
    1 1 1 1
    o
    o
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2 2 3 3
    oo
    oo
    oxo
    xox
    oxo
    
    예상 출력
    0