백준 16900번 이름 정하기 (JAVA)

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

16900번: 이름 정하기

저는 해당 문제를 KMP를 통해 문제를 해결하였습니다.

저의 실수는 KMP에서 제일 길게 매칭되는 부분을 리턴하였었는데, 문제를 다시 읽고 이해하여 fail배열의 마지막 인덱스의 값을 리턴해야하는 것을 알았습니다.

이유는 해당 문자열이 반복적으로 나와야하는데 접두사와 접미사가 얼마나 매칭되는지만이 중요하기 때문입니다.

 

 

package BOJ.String;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;

public class BOJ_16900 {
    private static long kmp(String s){
        char[] text = s.toCharArray();
        int tLength = s.length();
        int[] fail = new int[tLength];
        int j = 0;
        for(int i = 1 ; i < tLength ; i++){
            while(j > 0 && text[i] != text[j]){
                j = fail[j-1];
            }
            if(text[i] == text[j]){
                fail[i] = ++j;
            }
        }
        return fail[tLength-1];
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        Function<String,Long> stol = Long::parseLong;
        String s = str[0];
        long k = stol.apply(str[1]);
        long overlap = kmp(s);
        long result = s.length() + (k-1L) * (s.length() - overlap);
        System.out.println(result);
    }
}