[백준] 1305 - 광고 (Java)

[백준] 1305 - 광고 (Java)

문제

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

풀이/후기

 

코드

package KMP;

import java.io.*;

public class Problem1305 {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int L = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int lastPi = getLastPi(str);
        System.out.println(L - lastPi);
    }

    static int getLastPi(String str){
        int len = str.length();
        int j=0; 
        int[] pi = new int[len];

        for (int i=1; i<len; i++){
            //System.out.println(str.charAt(i));
            //System.out.println(str.charAt(j));

            while (j > 0 && str.charAt(j) != str.charAt(i)){
                j = pi[j-1];
            }

            if (str.charAt(j) == str.charAt(i)){
                pi[i] = ++j;
            }
        }
        return pi[len - 1];
    }
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/0bdc894b6f60ffe7052cdc0227c7d0665c4e6218

참고

https://maivve.tistory.com/205