백준 10266번 : 시계 사진들 - kmp

https://www.acmicpc.net/problem/10266

10266번: 시계 사진들

 

 

여러 개의 각도를 지닌 두개의 시계를 비교할 때

회전하였을 때 둘이 같아질 수 있는지 비교해야 문제를 해결할 수 있다.

 

시계의 각도가 360,000개 있기 때문에

이를 회전하면서 비교하는 방법을 찾는 것이 중요하다.

 

직접 큐를 만들어서 회전하면서 for문을 돌며 비교할 경우에는 36만 * 36만 번 연산해야 하기 때문에

문제를 해결할 수 없다.

대신 비교할 text를 두번 반복해서 두고 pattern을 그에대해 비교하면

회전을 하지 않고 회전한 효과를 얻을 수 있다.

 

 

문제풀이코드 C++

#include <iostream>

#define MAX_LEN 360'000
using namespace std;

int N;
bool text[MAX_LEN * 2], pattern[MAX_LEN];
int fail[MAX_LEN];

void getFail() {
    int j = 0;

    for (int i = 1; i < MAX_LEN; i++) {
        while (j > 0 && pattern[j] != pattern[i]) {
            j = fail[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            fail[i] = ++j;
        }
    }
}


bool kmp() {
    int j = 0;
    for (int i = 0; i < 2 * MAX_LEN; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (text[i] == pattern[j]) {
            if (j == MAX_LEN - 1) {
                return true;
            } else {
                j++;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        text[tmp] = 1;
        text[MAX_LEN + tmp] = 1;
    }

    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        pattern[tmp] = 1;
    }

    getFail();

    if (kmp()) {
        cout << "possible" << '\n';
    } else {
        cout << "impossible" << '\n';
    }
}