백준 : 1305 (광고) java

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

1305번: 광고

문제의 정답은  L - Pi[L-1]  이다 이것이 나타내는 것은 L이라는 문자열 안에 똑같은 패턴이 있다면 가장 짧은 패턴을 찾아내는 것이다.  물론 패턴의 길이 최대는 L 이다.

KMP 의 getPi 함수를 사용하면 접두사 접미사로 이루어져있고 문자열의 길이 마다 반복되는 문자열의 위치를 알 수 있다.

aaaaa -> 01234  이것을 이용해서 최대 패턴의 길이를 구할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1305 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		String pattern;
		int L;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		L = Integer.parseInt(br.readLine());
		pattern = br.readLine();

		int Pi[] = getPi(pattern);
		
		System.out.println(L-Pi[L-1]);
	}

	static int[] getPi(String Pattern) {
		int[] pi = new int[Pattern.length()];

		int j = 0;

		for (int i = 1; i < Pattern.length(); i++) {

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