티스토리 뷰

알고리즘 관련/BOJ

BOJ)10266 시계 사진들

JASON 자손9319 2017. 2. 8. 01:47

문제: icpc.me/10266


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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 > && 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 > && 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;
}
 
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14226 이모티콘  (0) 2017.02.14
BOJ)5398 틀렸습니다  (0) 2017.02.11
BOJ)10266 시계 사진들  (0) 2017.02.08
BOJ)1305 광고  (0) 2017.02.08
BOJ)11479 서로 다른 부분 문자열의 개수2  (0) 2017.02.08
BOJ)9249 최장 공통 부분 문자열  (0) 2017.02.08
TAG
댓글
댓글쓰기 폼