[알고리즘] 실패함수(문자열 검색 - KMP 알고리즘 관련)

4354번: 문자열 제곱 (acmicpc.net)

4354번: 문자열 제곱

 

이 문제 풀어보다가 시간 초과 때문에 넘어가질 않아서

 

고민하던 중 이건 이론적인 부분이 필요할 거 같다고 생각했다.

 

지금까지는 맨 땅에 삽질했는데 생각해보면 그냥 머리 풀기? 그런 용도지

 

실력적으로는 크게 향상이 없는 것 같아서 검색을 해야겠다 생각했다.

 

물론 내가 고민해서 알고리즘을 만들 수 있지만

 

애초에 그 정도 경지이면 여기서 이러고 있으면 안 되지;

 

독학사 공부할 때 잠깐 봤던 KMP나 라빈 코프 알고리즘이 생각이 났었는데

 

명칭이랑 간략한 설명 정도만 읽었지 어떻게 구현하는지는 모르니까

 

크게 와닿지 않아 내가 처음 작성한 코드를 끝까지 완성해야 지하고 조건 범위를 참고하고자

 

구글에 문자열 제곱을 검색했다. 근데 역시 사람들은 KMP 알고리즘을 사용해서 풀었다....

 

그냥 깔끔하게 인정하고 이 문제에 사용된 KMP 알고리즘의 실패 함수에 대해서 분석을 해봤다.

 

public 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));
		
		String str = br.readLine();
		
		char[] charArr = str.toCharArray();
		
		int[] arr = new int[charArr.length];
		
		int j = 0;
		
		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;
				
			}
			
		}
		
		for(int i = 0; i < arr.length; i++) {
			
			System.out.println(arr[i]);
			
		}

	}

}

여러 가지 예시를 보면서 실패 함수에 리턴하는 숫자는 무슨 의미를 지닐까 생각을 해봤다.

이런 식으로 리턴이 되는데

 

잘 보면 아래 숫자의 크기만큼의 string과

(자기 자신을 포함하여 인덱스를 감소시켰을 경우)

 

인덱스 0부터 위와 동일한 크기의 string이 일치함을 알 수 있다.

 

예시

이렇게 만들어진 실패 함수는 문자열을 검색할 때 큰 도움을 주는데

 

그건 나중에 KMP 알고리즘을 정리할 때 사용해보도록 하겠다.

 

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;
				
	}
			
}

여기부터는 구현에 대한 설명이다.

 

이렇게 시작하는데 j와 i가 일치를 하면 둘 다 증가하게 된다.

(i는 맞든 틀리든 증가 j는 연속적으로 일치하는지 알기 위해 증가)

 

만약 틀리게 되면 j가 0보다 크다면 실패 함수 arr에서 인덱스 j-1의 값으로 바뀐다.

(만약에 abac와 abab를 비교 중이었다면

 

둘은 불일치하더라도 후자의 ab와 전자의 ab가 일치하므로

 

abab의 다음에 나올 문자와 abac의 세 번째 문자와 비교를 하면 되기 때문이다)

 

이는 일치하거나 j의 값이 0이 될 때까지 반복된다.

 

이렇게 i가 문자열 전부를 검사하면 끝