단계별로 풀어보기(문자열 알고리즘1 - 광고)

1305번: 광고 (acmicpc.net)

1305번: 광고

http://boj.kr/fbb269256fb24400bd248ba50670fb37

공유 소스 보기

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

class Main{
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
 		int j = 0, panelStringLength = Integer.parseInt(br.readLine());       
        
		String str = br.readLine();
		
		char[] charArr = str.toCharArray();
		
		int[] arr = new int[charArr.length];
		
		for(int i = 1; i < charArr.length; i++) {
			
			while(j > 0 && charArr[j] != charArr[i]) {
				
				j = arr[j - 1];
				
			}
				
			if(charArr[j] == charArr[i]) {
				
				arr[i] = ++j;
				
			}
			
		}
		
		bw.write(String.valueOf(panelStringLength - arr[arr.length - 1]));
        bw.close();
    }
    
}

 

심심해서 단계별로 풀어보기 내려보다가

 

문자열 알고리즘 1이 진행 중으로 나오길래

 

??? 뭐지 하고 들어가 봤더니 전에 했던 문자열 제곱이

 

단계별로 풀어보기 문제 중 하나였던 것이다...

 

Botherahn :: 단계별로 풀어보기(문자열 알고리즘 1 - 문자열 제곱) (tistory.com)

단계별로 풀어보기(문자열 알고리즘1 - 문자열 제곱)

참조..

 

똑같이 실패 함수 이용하는 거라고 쓰여있길래

 

봤는데 그냥 전광판 문자 길이와 실패 함수 마지막 숫자를 빼주면

 

되는 것 같아 실행했더니 성공했다.

 

문자열 제곱은 문자열이 주어졌을 때

 

문자열 제곱의 정의에 따라

 

이 문자열이 어떤 문자열을 제곱했느냐의 여부를 판별하는 문제였다.

 

따라서 이를 역 이용하면 광고에서의 문자열은

 

처음 주어진 광고 문자열의 길이의 안에서

 

aaba든 abaa든  baaa든 어차피 차례대로 반복되기에

 

마지막 문자의 실패 함숫값을 통해

 

얘가 어느 정도 반복되었는가를 알아낼 수 있다.

(aaba, abaa, baaa, aaab 얘네 다 같은 걸로 보는 거임)

 

결론적으로 전체 길이에서 마지막 문자의 실패 함숫값을 빼주면

 

반복되는 문자열의 길이를 알 수 있다.