백준 10266 - 시계 사진들 (Python)

시계는 원형이라 a를 두번 이어 붙인 후 b를 KMP알고리즘을 통해 찾으면 해결할 수 있습니다.

전체 코드

import sys

input = sys.stdin.readline

def make_table(p):
    t = [0] * len(p)
    j = 0

    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = t[j - 1]
        
        if p[i] == p[j]:
            j += 1
            t[i] = j

    return t

def find(s, p):
    t = make_table(p)
    j = 0

    for i in range(1, len(s)):
        while j > 0 and s[i] != p[j]:
            j = t[j - 1]
        
        if s[i] == p[j]:
            if j == len(p) - 1:
                return True
            else:
                j += 1

    return False
                
n = int(input())
a = [0] * 360000
b = [0] * 360000

for i in map(int, input().split()):
    a[i] = 1
for i in map(int, input().split()):
    b[i] = 1

a += a

if find(a, b):
    print('possible')
else:
    print('impossible')