KMP 알고리즘 [펌-요약]

먼저 알아야 하는 것

---

KMP 알고리즘을 이해하기 위해 먼저 알아야 하는 것이 2가지가 있습니다.

첫번째는 접두사(prefix)와 접미사(suffix)입니다.

직관적으로 "banana"의 접미사와 접두사를 보면 무엇인지 이해될 것 입니다.

<banana의 접두사>

b

ba

ban

bana

banan

banana

이 6개가 banana의 접두사(prefix) 입니다.

<banana의 접미사>

a

na

ana

nana

anana

banana

이 6개가 banana의 접미사(suffix) 입니다.

두번째로 pi배열 입니다.

pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이

(이때 prefix가 0~i  까지의 부분 문자열과 같으면 안된다.)

무슨 말인지 모르겠죠? 예시를 보면 직관적으로 이해할 수 있을 겁니다.

먼저 문자열 "ABAABAB"의 pi배열을 구해봅시다.

i	부분 문자열	pi[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

한번 더 "AABAA"의 pi배열을 구해봅시다.

i	부분 문자열	pi[i]
0	A	0
1	AA	1
2	AAB	0
3	AABA	1
4	AABAA	2

이제 KMP알고리즘을 이해하기 위해 필요한 지식을 갖췄습니다!

단순한 방법은 정보를 낭비하고 있다!

---

위에서 설명한 단순한 방법은 진행과정 중에 발생한 멋진 정보를 낭비하고 있습니다.

어떤 정보를 낭비하고 있다는 걸까요?

텍스트 "ABCDABCDABDE"에서 패턴 "ABCDABE"를 찾는 상황을 생각해봅시다.

같니?

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C

D

A

B

E

E

패턴

A

B

C

D

A

B

E

->달라!

첫번째 시도에서 패턴의 0~5부분 문자열("ABCDAB")는 텍스트와 일치했지만 6번째 인덱스의 E가 텍스트와 일치하지 않았습니다.

단순한 방법은 그 후 두번째 시도에서 이렇게 진행합니다.

같니?

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C

D

A

B

E

E

패턴

A

B

C

D

A

B

E

->달라!

첫번째 시도에서 두번째 시도로 넘어갈때 지금까지 발견한 멋진 정보를 사용하지 않았다는게 보이나요?

prefix == suffix 정보를 활용해서, 다음시작 인덱스는 4가 되어 아래 단계로 넘어갈 수 있다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C (i)

D

A

B

E

E

패턴

A

B

C (j)

D

A

B

E

출처: http://bowbowbow.tistory.com/6 [멍멍멍]