BOJ)10266 시계 사진들

문제: icpc.me/10266

각 시계의 바늘들을 1 빈 공간을 0으로 표시해준 뒤 환형 문자열 A에서 B를 탐색하여 존재하는 경우 possible을 출력하면 된다.

환형 문자열 A를 탐색하는 방법은 A 2개를 이어붙인 문자열에서 B를 탐색하면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define N 360000
using namespace std;
int n, f, t;
bool arr[720100];
bool brr[360100];
int pi[360100];
void getpi(){
    int j = 0;
    for (int i = 1; i < N; i++){
        while (j > 0 && brr[i] != brr[j])
            j = pi[j - 1];
        if (brr[i] == brr[j])
            pi[i] = ++j;
    }
}
void kmp(){
    int j = 0;
    for (int i = 0; i < 2*N; i++){
        while (j > 0 && arr[i] != brr[j])
            j = pi[j - 1];
        if (arr[i] == brr[j]){
            if (j == N - 1){
                f = true;
                break;
            }
            else
                j++;
        }
    }
    if (f)
        printf("possible");
    else
        printf("impossible");
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &t);
        arr[t] = 1;
        arr[t + N] = 1;
    }
    for (int i = 0; i < n; i++){
        scanf("%d", &t);
        brr[t] = 1;
    }
    getpi();
    kmp();
    return 0;
}