은기의 아주 큰 그림

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWkIfv7qBCYDFAXC&categoryId=AWkIfv7qBCYDFAXC&categoryType=CODE&problemTitle=%EC%9D%80%EA%B8%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

시간 제한이 1초이므로

브루트포스로 비교를 하면 시간 초과가 난다.

 

라빈 카프 알고리즘을 이용한다.

<2차원 배열 해싱>

가로 해싱을 하고

세로 해싱을 해준다.

중요한 것은

해시값을 다르게 줘야한다!!

같게 주면 대칭 구조가 나올 수 있다.

 

은기의 그림을 해싱.

 

 

선생님의 그림을 해싱

 

2중 포문 돌려서 해시 값 비교로 끝내면 된다.

 

 

<소스 코드>

#include <iostream>
 
using namespace std;
 
int mod = ((1 << 30) - 1);
 
int ePic[2001][2001];
int tPic[2001][2001];
int tmp[2001][2001];
int cmp_hash[2001][2001];
 
int Hashing(int* arr, int lim, int kugi)
{
    int hash = 0;
    for (int i = 0; i < lim; i++)
    {
        hash += (hash << kugi) + *arr;
        arr++;
    }
 
    return (int) (hash & mod);
}
 
inline int Calc(int lim, int kugi)
{
    int x = 1;
    for (int i = 1; i < lim; i++)
        x += (x << kugi);
 
    return (int) (x & mod);
}
 
int T_Hashing(int prev_h, int minus, int hash_v, int add, int kugi)
{
    int hash = prev_h - (minus * hash_v);
    hash += (hash << kugi) + add;
    return (int)(hash & mod);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int test;
    cin >> test;
 
    for (int t = 1; t <= test; t++)
    {
        int h, w, n, m;
        cin >> h >> w >> n >> m;
 
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                char c;
                cin >> c;
                if (c == 'o')
                    ePic[i][j] = 1;
                else
                    ePic[i][j] = 0;
            }
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                char c;
                cin >> c;
                if (c == 'o')
                    tPic[i][j] = 1;
                else
                    tPic[i][j] = 0;
            }
        }
 
 
        // 가로 해싱
        for (int i = 0; i < h; i++)
        {
            tmp[0][i] = Hashing(ePic[i], w, 4);
        }
        // 세로 해싱
        int myHash = Hashing(tmp[0], h, 5);
 
 
        int garo = Calc(w, 4);
        int sero = Calc(h, 5);
 
        // 선생님 가로 해싱
        for (int i = 0; i < n; i++)
        {
            tmp[0][i] = Hashing(tPic[i], w, 4);
            // 하나 빼기
            for (int j = 1; j < m - w + 1; j++)
            {
                tmp[j][i] = T_Hashing(tmp[j - 1][i], tPic[i][j - 1], garo, tPic[i][j + w - 1], 4);
            }
        }
 
        // 선생님 세로 해싱
        for (int i = 0; i < m - w + 1; i++)
        {
            cmp_hash[0][i] = Hashing(tmp[i], h, 5);
            // 하나 빼기
            for (int j = 1; j < n - h + 1; j++)
            {
                cmp_hash[j][i] = T_Hashing(cmp_hash[j - 1][i], tmp[i][j - 1], sero, tmp[i][j + h - 1], 5);
            }
        }
 
 
        int ans = 0;
        for (int i = 0; i < n - h + 1; i++)
        {
            for (int j = 0; j < m - w + 1; j++)
            {
                if (cmp_hash[i][j] == myHash)
                    ans++;
            }
        }
 
        cout << '#'<< t << ' ' << ans << '\n';
    }
 
    return 0;
}