KMP : 문자열 검색 알고리즘

문자열 검색이 뭐지?

---

워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 

브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다.

아래 이미지는 브라우저에서 "테이프"를 검색했을 때 결과를 캡쳐한 것입니다. 본문에서 89개의 "테이프"를 찾았다고 순식간에 알려주네요.

이렇게 텍스트내(본문)에서 특정 문자열, 패턴("테이프")를 찾는 것을 문자열 검색이라고 부릅니다.

이 문자열 검색은 어떤 방식으로 구현되는걸까요?

가장 단순한 문자열 검색

---

먼저 가장 단순한 방법의 문자열 검색을 생각해봅시다.

텍스트 "ABCABABCDE"에서 패턴 "ABC"가 어디서 등장하는지 찾아봅시다.

패턴 "ABC"를 한자리씩 옮기면서 같은지 비교합니다.

같아?

A	B	C	A	B	A	B	C	D	E
A	B	C

->같아!

같아?

A	B	C	A	B	A	B	C	D	E
	A	B	C

->달라!

같아?

A	B	C	A	B	A	B	C	D	E
		A	B	C

->달라!

같아?

A	B	C	A	B	A	B	C	D	E
			A	B	C

->달라!

같아?

A	B	C	A	B	A	B	C	D	E
				A	B	C

->달라!

같아?

A	B	C	A	B	A	B	C	D	E
					A	B	C

->같아!

같아?

A	B	C	A	B	A	B	C	D	E
						A	B	C

->달라!

같아?

A	B	C	A	B	A	B	C	D	E
							A	B	C

->달라!

위와 같은 과정을 진행했을 때 

텍스트 "ABCABABCDEFAAAB"에서 패턴 "ABC"는 밑줄친 자리에서 총 두번 등장함을 알 수 있습니다.

ABCABABCDE

이 과정의 시간 복잡도는 텍스트의 길이를 N, 패턴의 길이를 M이라 할 때 각 텍스트의 인덱스에 대해 패턴이 일치하는지 비교하므로 O(NM)입니다.

이 보다 더 빠르고 효율적으로 하는 방법은 없을까요?

있습니다! KMP 알고리즘을 이용하면 O(N+M)에 문자열 검색을 할 수 있습니다.

KMP 알고리즘이란?

---

KMP알고리즘은 만든 사람이름이 Knuth, Morris, Prett이기 때문에 앞글자를 하나씩 따서 KMP알고리즘이라 이름 붙었습니다.

KMP알고리즘의 시간 복잡도는 O(N+M)으로 위의 무식한 방법 O(NM) 보다 매우 빠릅니다.

단순한 방법에서 개선할 수 있는 여지가 보이지 않는데요.. 도대체 무슨 짓을 하길레 이렇게 빠르게할 수 있을까요? 

그 비법을 파헤쳐봅시다.

먼저 알아야 하는 것

---

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알고리즘을 이해하기 위해 필요한 지식을 갖췄습니다!

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

---

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

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

텍스트 "ABCDABCDABEE"에서 패턴 "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

->달라!

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

첫번째 시도에서 알게된건 아래 박스친 부분이 틀렸다는 사실만이 아닙니다.

또 알수있는 사실, 즉 지금까지 낭비하고 있었던 정보는 아래 박스친 부분은 일치한다는 사실입니다.

이 정보를 십분 활용해서 검색 속도를 개선하는것이 바로 KMP알고리즘의 핵심 비법입니다.

일치했다는 사실을 어떻게 활용할 것인가

---

위 정보를 활용한 결과 이 상태에서 

중간 시도를 껑충~! 건너띄고 

바로 아래 단계로 넘어갈 수 있습니다. (i는 텍스트의 현재 비교위치, j는 패턴의 현재 비교위치를 나타내는 변수입니다.)

인덱스

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

그게 가능한 이유는 일치했던 "ABCDAB"에서 파란색 박스로 표시한 접두사(prefix) AB와 접미사(suffix) AB가 일치하기 때문입니다. 또한 이것이 접두사와 접미사가 일치하는 최대 길이이기 때문입니다. 이 값이 바로 패턴 "ABCDABE"의 pi[5] =2 값입니다.

아래에 껑충 건너띈 단계를 자세히 나타냈습니다.

중간 단계인 아래 단계를 시도해볼 필요가 없습니다. 이 단계에서 패턴이 일치하려면 적어도 pi[5]= 5여야 했기 때문입니다.

인덱스

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

또 중간 단계인 아래 단계를 시도해볼 필요가 없습니다. 이 단계에서 패턴이 일치하려면 적어도 pi[5]= 4여야 했기 때문입니다.

인덱스

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

또 중간 단계인 아래 단계를 시도해볼 필요가 없습니다. 이 단계에서 패턴이 일치하려면 적어도 pi[5]= 3여야 했기 때문입니다.

인덱스

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

또 i는 텍스트의 현재 비교위치, j는 패턴의 현재 비교위치를 나타내는 변수일 때 i, j를 여기서 시작할 필요가 없습니다.

p[5] = 2라는 정보는 접미사 AB가 접두사 AB와 같다는 것을 말하므로 패턴 "ABCDABE"에서 "AB"는 이미 텍스트와 일치함을 알 수  있기 때문입니다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A (i)

B

C

D

A

B

E

E

패턴

A (j)

B

C

D

A

B

E

이렇게 kmp 알고리즘은 틀렸다는 사실이 아니라 조금이라도 일치했었다는 정보에 주목하고 미리 전처리 해둔 pi배열을 이용해서 많은 중간 시도를 껑충 건너띌 수 있게 합니다.

지금까지 전반적인 kmp알고리즘의 원리를 살펴봤습니다. 이제 어떻게 kmp를 구현하는지 살펴봅시다.

KMP의 구현

---

kmp알고리즘의 

크게 주어진 패턴에 대해 pi배열을 얻는 getPi함수와 pi배열을 이용해 문자열 검색을 시행하는 kmp함수로 나누어 구현했습니다.

kmp 알고리즘을 전형적으로 사용하는 문제인 백준온라인저지 1786번 : 찾기 문제의 입출력에 대한 kmp알고리즘 코드를 작성하겠습니다.

(코드에 등장하는 auto 는 c++11에서 자료형을 자동으로 지정해주는 식별자입니다.)

위 코드에서 kmp함수와 getPi함수가 구체적으로 어떻게 작동하는지 설명하겠습니다.

kmp 함수 구현

---

저도 위 함수에서 6~7번 라인이 이해하기 어려웠습니다.

whlie(j>0 & s[i] != p[j])

j = p[j-1];

는 위에서 설명한 것 처럼 일치했던 정보와 pi배열을 이용해서 중간 단계를 껑충 뛰어넘는 부분입니다.

그런데 한 번만 j = p[j-1]해주면 될거 같은데 왜 while문 안에서 조건을 만족할 때 까지 반복되도록 했을까요?

그 이유는 주어진 정보로 최대한 중간 단계를 뛰어 넘기 위해서 입니다. 아래 예시를 보면서 이해합시다.

텍스트 : "ABABABABBABABABABC"에서 패턴 "ABABABABC"를 찾는 상황입니다.

왜 중간단계를 뛰어넘는것을 여러번 해야하는지 아례 예시로 나타냈습니다. i = 8일 때 while문 내부가 실행되는 모습입니다.

첫번째 시도에서 패턴의 마지막 문자가 일치하지 않았지만 "ABABABAB" 부분이 텍스트와 일치하여 pi[7] = 6값을 이용해 중간 단계를 점프합니다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

텍스트

A

B

A

B

A

B

A

B

B (i)

A

B

A

B

A

B

A

B

C

패턴

A

B

A

B

A

B

A

B

C (j)

점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 여기서 하지만 패턴 "ABABAB"가 일치하므로 pi[6]= 4를 이용해서 다시한번 점프할 수 있습니다. 

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

텍스트

A

B

A

B

A

B

A

B

B (i)

A

B

A

B

A

B

A

B

C

패턴

A

B

A

B

A

B

A (j)

B

C

점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 여기서 하지만 패턴 "ABAB"가 일치하므로 pi[3]= 2를 이용해서 다시한번 점프할 수 있습니다. 

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

텍스트

A

B

A

B

A

B

A

B

B (i)

A

B

A

B

A

B

A

B

C

패턴

A

B

A

B

A (j)

B

A

B

C

또 점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 이제 pi[1] = 0이므로 다시 점프합니다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

텍스트

A

B

A

B

A

B

A

B

B (i)

A

B

A

B

A

B

A

B

C

패턴

A

B

A (j)

B

A

B

A

B

C

다음 단계로 넘어갑니다. 다음과 같이 i가 증가해서 다음 스텝으로 넘어가고 j =0 이 되었습니다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

텍스트

A

B

A

B

A

B

A

B

B

A (i)

B

A

B

A

B

A

B

C

패턴

A (j)

B

A

B

A

B

A

B

C

while문 안을 제외한 부분은 위에서 설명한 부분을 통해 코드를 직접 읽으면서 이해하기 바랍니다.

getPi 함수 구현

---

getPi 함수는 kmp함수와 매우 유사하지 않나요?

먼저 getPi함수를 가장 단순한 방법으로 구현하면 Pi배열을 얻으려는 패턴의 길이를 m이라 할 때 O(m^3)의 시간이 필요합니다.

텍스트는 대부분 길지만 찾으려는 패턴의 길이는 대부분 짧기 때문에 m^3도 충분한 시간이지만 kmp의 원리를 Pi배열을 얻을 때도 사용하면

Pi배열 생성 시간을 O(m) 으로 비약적으로 시간을 단축할 수 있습니다.

위 코드는 O(m) 시간복잡도를 가지는 코드입니다. 

먼저 패턴 "ABABABAC"의 Pi배열의 생성 과정을 쭉 나열해보겠습니다.

P[1]과 P[0]이 일치하지 않아서 Pi[1] = 0이 저장됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0
패턴 P	인덱스	0	1 (i)	2	3	4	5	6	7
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스		0 (j)	1	2	3	4	5	6	7
	값		A	B	A	B	A	B	A	C

P[2]와 P[0]가 일치해서 P[2] = 1이 저장됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1
패턴 P	인덱스	0	1	2 (i)	3	4	5	6	7
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스			0 (j)	1	2	3	4	5	6	7
	값			A	B	A	B	A	B	A	C

P[3]와 P[1]가 일치해서 P[3] = 2가 저장됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2
패턴 P	인덱스	0	1	2	3 (i)	4	5	6	7
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스			0	1 (j)	2	3	4	5	6	7
	값			A	B	A	B	A	B	A	C

P[4]와 P[2]가 일치해서 P[4] = 3가 저장됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3
패턴 P	인덱스	0	1	2	3	4 (i)	5	6	7
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스			0	1	2 (j)	3	4	5	6	7
	값			A	B	A	B	A	B	A	C

P[5]와 P[3]가 일치해서 P[5] = 4가 저장됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4
패턴 P	인덱스	0	1	2	3	4	5 (i)	6	7
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스			0	1	2	3 (j)	4	5	6	7
	값			A	B	A	B	A	B	A	C

P[6]와 P[4]가 일치해서 P[6] = 5가 저장됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4	5
패턴 S	인덱스	0	1	2	3	4	5	6 (i)	7
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스			0	1	2	3	4 (j)	5	6	7
	값			A	B	A	B	A	B	A	C

P[7]와 P[5]가 불 일치해서 j를 j = Pi[4] 을 대입해 j 인덱스를 앞으로 당깁니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4	5
패턴 P	인덱스	0	1	2	3	4	5	6	7 (i)
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스			0	1	2	3	4	5 (j)	6	7
	값			A	B	A	B	A	B	A	C

P[7]와 P[3]이 또 불 일치해서 j를 j = Pi[2] 을 대입해 j 인덱스를 앞으로 당깁니다. 즉 중간단계를 pi배열을 이용해 점프합니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4	5
패턴 P	인덱스	0	1	2	3	4	5	6	7 (i)
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스					0	1	2	3 (j)	4	5	6	7
	값					A	B	A	B	A	B	A	C

P[7]와 P[1]이 또 불 일치해서 j를 j = Pi[0] 을 대입해 j 인덱스를 앞으로 당깁니다.  즉 중간단계를 pi배열을 이용해 점프합니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4	5
패턴 S	인덱스	0	1	2	3	4	5	6	7 (i)
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스							0	1 (j)	2	3	4	5	6	7
	값							A	B	A	B	A	B	A	C

P[7]와 P[0]이 또 불 일치해서 j는 인덱스 0으로 그대로 유지됩니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4	5	0
패턴 P	인덱스	0	1	2	3	4	5	6	7 (i)
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스								0 (j)	1	2	3	4	5	6	7
	값								A	B	A	B	A	B	A	C

i가 패턴의 길이 7보다 커져서 종료합니다.

Pi	인덱스	0	1	2	3	4	5	6	7
	값	0	0	1	2	3	4	5	0
패턴 P	인덱스	0	1	2	3	4	5	6	7	8 (i)
	값	A	B	A	B	A	B	A	C
패턴 P	인덱스									0 (j)	1	2	3	4	5	6	7
	값									A	B	A	B	A	B	A	C

위 과정을 통해 Pi배열을 구할 때도 kmp원리를 이용한 것을 확인할 수 있습니다.