KMP 그림 그리면서 구현

KMP의 Motivation이 무엇인지는 다른 곳에서 쉽게 찾아볼 수 있으니 여기에 굳이 설명을 적지는 않는다. KMP의 까다로운 점은 저 Motivation을 다 알아도 수많은 edge case들 때문에 구현하기가 상당히 까다롭다는 것이다. 유한 오토마타의 개념을 알고 있으면 KMP를 상당히 직관적으로 구현할 수 있다. 일단 ABABCABAC에 대응되는 실패 함수 배열을 살펴보자.

 

	A	B	A	B	C	A	B	A	C
pi	0	0	1	2	0	1	2	3	0

실패 함수 := 문자열 s[0:i] 2개를 얼마나 겹치게 놓을 수 있느냐를 숫자로 나타낸 값. 예) i = 7일 때 문자열은 ABABCABA인데 이걸 카피 떠서 하나 더 만들면 ABABCABA ABABCABA임. 그런데 앞 문자열의 뒤 3개랑 뒤 문자열의 앞 3개가 겹친다. 따라서 pi[7] = 3.

이름이 왜 실패함수냐?) 7의 위치에서 실패하면 3으로 가야 돼서 그럼.

 

 i = 0일 때는 정의상 무조건 0이다.

 

실패 함수 어떻게 만듦?

 

(참고로 실패했을 때 실패함수가 가리키는 곳으로 가야 한다고 되어 있는데, 그림에서도 볼 수 있지만 참조해야 하는 인덱스가 지금 보고 있는 인덱스의 한 칸 뒤다. 넷째 줄에서 박스가 k = 3을 보고 있고 여기서 실패했는데, 참조해야 하는 실패함수는 pi[3]이 아니라 pi[2]임.)

 

 실패함수로 KMP 어떻게 만듦?

 

그냥 이 Non-deterministic Finite Automata를 그대로 구현하면 된다. 파란색은 실패함수, 검은색은 move, 핑크색은 null move.

 

반전) 저 그림은 사실 KMP에 완벽 대응하는 오토마타가 아니다. "갈 데가 없을 때만 null move를 써라"라는 규칙을 추가해야만 KMP에 완벽 대응하는 그림이 되는데, 문제는 그런 규칙이 있으면 일단 오토마타가 아니기 때문에...