흙금이네 블로그

아이디어 문자열의 접두사와 접미사가 겹치는 부분의 길이만큼 줄일 수 있다. 풀이 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)