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

 

 

아이디어

 

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

 

 

풀이

 

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)