흙금이네 블로그

[BOJ] 16900 - 이름 정하기 (Python) 본문

알고리즘

[BOJ] 16900 - 이름 정하기 (Python)

흙금 2023. 1. 16. 00:40

 

 

아이디어

 

문자열의 접두사와 접미사가 겹치는 부분의 길이만큼 줄일 수 있다.

 

 

풀이

 

KMP 알고리즘으로 부분 일치 테이블 lps를 만든 후,

문자열 S의 길이 N을 K번 더한 값에서 접두사와 접미사가 일치하는 부분 lps[-1]을 K-1번 더한 값을 빼준다.

 

S, K = input().split()
K = int(K)
N = len(S)
lps = [0]*N
j = 0
for i in range(1, N):
    while j > 0 and S[i] != S[j]:
        j = lps[j-1]
    if S[i] == S[j]:
        j += 1
        lps[i] = j
res = N+(N-lps[-1])*(K-1)
print(res)

 

'알고리즘' 카테고리의 다른 글

[BOJ] 21918 - 전구 (Python, JavaScript)  (0) 2023.01.16
[BOJ] 16570 - 앞뒤가 맞는 수열 (Python)  (0) 2023.01.16
[BOJ] 1786 - 찾기 (Python)  (0) 2023.01.15
[BOJ] 1525 - 퍼즐 (Python)  (0) 2023.01.14
[BOJ] 1781 - 컵라면 (Python)  (1) 2023.01.14
Comments