KMP 알고리즘을 공부하다 도저히 p배열이 이해가 안되서 나름대로 정리 해보았다.

정의

설명하기 앞서 먼저 정의해야 할 것이 있다.

1. 문자열 s의 prefix와 suffix는 항상 같다.
2. p[index]은 prefix의 길이를 나타낸다.
3. 크기가 x인 s는 index (x-1)의 s이다.

예시로 보는 풀이

예제로 설명한다.
ABAABAB의 p배열을 구해보자.

prefix는 빨강, suffix는 파랑으로 표시했다.

index	s	p
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

기본적으로는 다음 값이 추가되면 prefix의 다음과 비교해서 prefix 크기를 늘릴지 결정한다. (index 3 -> 4 같은 경우)

만약 다음값이 prefix의 다음과 다르다면, 지금부터 설명할 기법을 사용해야 한다.

p를 이용해 부분 prefix로 검색

이해하기 쉽게 index 5에서 index 6으로 갈때 과정을 알아보자.
ABAABA에서 B가 추가되었으니

ABAA와 ABAB를 비교한다.
A와 B가 같지 않으니 둘은 같지 않다.

맨 처음의 A부터 다시 비교해야 할까?
그럴 필요가 없다!

prefix와 suffix의 부분적으로 같은 문자열이 있기 때문이다!
처음부터 비교하지 않고 ABAABA에서 다시 비교하면 된다.
AB와 AB를 비교한다.

두 문자열이 같으니 index 6은
ABAABAB가 된다.

이게 어떻게 가능할까?

prefix의 prefix와 suffix를 prefix(p), suffix(p)라고 하고
suffix의 prefix와 suffix를 prefix(s), suffix(s)라고 하겠다.

정의에 의해서 아래는 모두 참이다.
prefix(p) = suffix(p)
prefix(s) = suffix(s)

정의에 의해서 prefix = suffix는 참이니
prefix(p) = suffix(s)이다.

따라서 우리는 prefix, suffix를 prefix(p), suffix(s)로 갱신해야 한다.

이는 아래의 공식으로 구할 수 있다.
prefix(p) = suffix(s) = index (p[index] - 1)의 s이다.

이번에도 index 5에서 index 6으로 갈때를 예시로 들어 설명한다.
ABAABA -> ABAABAB

ABA의 prefix는 p배열을 이용해 구할 수 있다.

일단 ABA는 크기가 3 (p[5]=3) 이고
index (3-1 = 2)일 때의 s인 ABA와 같다.

따라서 ABA는 ABA이니 ABA의 prefix는 A다.

다시 ABAABA로 돌아가서
AB와 AB를 비교한다.

둘의 값이 같으니
index 6은 ABAABAB가 된다.