[백준] 16900. 이름 정하기(Java)

문제

https://www.acmicpc.net/problem/16900

 

 

풀이

KMP 알고리즘을 사용하는 문제입니다.
가장 짧은 문자열을 구하기 위해서는 두개를 최대한 많이 겹쳐내야 합니다. 이를 실패 배열을 통해 찾아냈습니다.

실패 배열의 값은 접두사와 접미사가 같아지는 최대 길이를 의미합니다.
예를들어, ada에서 0번째 인덱스와 2번째 인덱스는 접두사와 접미시가 일치하는 부분이며

이러한 일치하는 길이는 1입니다.
table[N-1]는 문자열 마지막 인덱스 위치까지, 사이에 겹쳐지는 길이의 최댓값을 의미합니다.

이를 바탕으로, N + (K - 1L) * (N - table[N-1])를 구해줍니다.
원본 문자열 길이 + (몇 번 반복 - 1) * (원본 문자열 길이 - 접두사와 접미시가 최대로 겹쳐지는 수)
(몇 번 반복 - 1)에서 -1을 빼주는 이유는 원본 문자열을 따로 세기 때문입니다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] table;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        String s = st.nextToken();
        N = s.length();
        int K = Integer.parseInt(st.nextToken());

        // 접두사와 접미사가 같아지는 최대 길이를 담는 값
        // table[N-1] = 문자열 마지막 인덱스 위치까지, 사이에 겹쳐지는 길이의 최댓값
        // 문자열 두개를 최대한 많이 겹쳐낼 수록 길이가 짧아짐
        table = new int[N];

        makeTable(s);

        long res = N + (K - 1L) * (N - table[N-1]);
        System.out.println(res);
    }

    public static void makeTable(String s) {
        int idx = 0;
        for (int i = 1; i < N; i++) {
            while (idx > 0 && s.charAt(idx) != s.charAt(i)) {
                idx = table[idx - 1];
            }
            if (s.charAt(idx) == s.charAt(i)) {
                table[i] = ++idx;
            }
        }
    }
}