[BOJ] 12104 - 순환 순열 (Python)

 

 

아이디어

 

A와 B를 XOR했을 때 0이 나오려면 두 수가 같아야 한다.

순환 순열이므로 A를 두 배로 늘린 문자열에서 B의 개수를 찾는다.

 

 

풀이

 

A와 B 두 문자열을 입력 받을 때, A는 두 번 반복하도록 한 후 함수 find를 호출하여 그 반환값을 출력한다.

 

함수 find에서는 B의 길이를 N에 저장하고 B의 부분 일치 테이블 lps를 구한다.

두 배로 늘린 A에서 인덱스 1부터 시작하여 B를 찾고, 그 개수를 res에 저장하여 반환한다.

현재 A는 원래 입력 받은 A를 두 번 반복하도록 했으므로 처음과 끝의 중복 계산을 막기 위해 인덱스 1부터 시작한다.

 

def find():
    N = len(B)
    lps = [0]*N
    j = 0
    for i in range(1, N):
        while j > 0 and B[i] != B[j]:
            j = lps[j-1]
        if B[i] == B[j]:
            j += 1
            lps[i] = j
    j = res = 0
    for i in range(1, N*2):
        while j > 0 and A[i] != B[j]:
            j = lps[j-1]
        if A[i] == B[j]:
            j += 1
            if j >= N:
                j = lps[j-1]
                res += 1
    return res

A = input()*2
B = input()
print(find())

 

 

lps와 결과값을 구하는 부분을 함수 find로 따로 빼지 않은 코드는 더 느렸다.

# 더 느린 코드
A = input()*2
B = input()
N = len(B)
lps = [0]*N
j = 0
for i in range(1, N):
    while j > 0 and B[i] != B[j]:
        j = lps[j-1]
    if B[i] == B[j]:
        j += 1
        lps[i] = j
j = res = 0
for i in range(1, N*2):
    while j > 0 and A[i] != B[j]:
        j = lps[j-1]
    if A[i] == B[j]:
        j += 1
        if j >= N:
            j = lps[j-1]
            res += 1
print(res)