1305 광고

 

 

1. 풀이

 

다른 블로그를 참고했다.

 

kmp 알고리즘에는 주어진 문자열의 

부분 문자열 중 접두사와 접미사가 같은 최대 길이를 나타내는 배열을 구한다.

나는 이를 value 배열이라고 표현했다.

 

이 문제에서 나온

문자열 aabaaa의 value 배열은

[0, 1, 0, 1, 2, 2] 이다.

 

kmp 알고리즘에 대해 자세히 알고 싶다면 다음 내용을 살펴보면 된다.

 

https://happy-fun.tistory.com/253

1786 찾기

 

 

그렇다면 이 문제의 정답은 L - value[L-1] 을 구하면 된다.

 

그 이유를 설명해 보겠다.

 

전광판에 나타나는 aabaaa에서

원래 광고하고 싶은 내용은 aaba 이다.

 

즉, aaba 에 aa가 붙었다.

그리고 aa는 원래 문자 aaba의 맨 앞부분이다.

 

즉 aa 가 원래 문자 aaba 앞 부분과 같기 때문에  

이 두 문자가 합쳐진 

aabaaa 에서 접두사와 접미사가 같은 부분이 생겨나게 되고,

이 부분을 나타내는 게 value[L-1] 이다.

 

value[L-1] = value[5] = 2 

즉, 원래 문자열에서 덧붙여진 문자 길이 2를 value[5] 가 나타내고 있다.

 

그렇기 때문에 전광판에 나타나는 문자(aabaaa)의 길이 L 에서

value[L-1] 을 빼면 되는 것이다.

 

문제에 나온 예제

aaaaa는,

 

원래 문자 a에 aaaa가 붙어서

최종 문자 aaaaa에서 

접두사와 접미사가 같은 부분이 aaaa로,

길이가 4이고

5 - 4 = 1 이 된다.

 

 

 

2. 최종 코드

 

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

public class Main {

	static int value[];
	static int L;
	static String input;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		L = Integer.parseInt(br.readLine());
		input = br.readLine();
		value = new int[L];
		makeValue();
		System.out.println(L-value[L-1]);
		
	}
	
	
	
	public static void makeValue() {
		
		int index = 0;
		
		for(int i = 1; i<L ; i++) {
			
			while(index >0 && input.charAt(i)!= input.charAt(index)) {
				index = value[index-1];
			}
			
			if(input.charAt(i)== input.charAt(index)) {
				index++;
				value[i] = index;
			}
			
		}
	}
}

 

참고 블로그 : 

https://hi-spring-night.tistory.com/21

[백준] 1305. 광고(JAVA)