KMP 알고리즘

KMP알고리즘

백준저지 

[찾기] https://www.acmicpc.net/problem/1786

본 문제를 해결하기 위해서는 KMP알고리즘에 대해 학습이 되어야한다. 

(참고로 전 이 알고리즘을 이해하는데 2주가 걸렸다는... T^T...)

먼저 이 알고리즘은 '찾기' 흔히 [CTRL] + [F]를 눌러 문자열 검색을 하는 기능에 필수적으로 들어가는 알고리즘이다. 

KMP는 Knuth, Morris, Prett의 사람 이름 앞자를 따서 만든 이름이다.

흔히 찾기 알고리즘을 구현하라고 하면 아래와 같은 방식으로 구현을 할 수 있을것이다.

"ABCDEF"란 Text에서 "CD"란 Pattern을 찾는다고 한다면,

	0	1	2	3	4	5
Text	A	B	C	D	E	F
	0	1
Pattern	C	D

Text[0]과 Text[1]이 Pattern[0]과 Pattern[1] 같은지를 비교

	0	1	2	3	4	5
Text	A	B	C	D	E	F
		0	1
Pattern		C	D

Text[1]과 Text[2]이 Pattern[0]과 Pattern[1] 같은지를 비교,

	0	1	2	3	4	5
Text	A	B	C	D	E	F
			0	1
Pattern			C	D

Text[2]과 Text[3]이 Pattern[0]과 Pattern[1] 같은지를 비교,

	0	1	2	3	4	5
Text	A	B	C	D	E	F
				0	1
Pattern				C	D

Text[3]과 Text[4]이 Pattern[0]과 Pattern[1] 같은지를 비교,

	0	1	2	3	4	5
Text	A	B	C	D	E	F
					0	1
Pattern					C	D

Text[4]과 Text[5]이 Pattern[0]과 Pattern[1] 같은지를 비교를 하게된다.

즉, 2번씩(Pattern의 길이) 5번(Text의 길이) 총 10번(Pattern의 길이 * Text의 길이)의 비교를 하게되는 것이다.

이거를 시간 복잡도로 일반화 해보면, Text의 길이를 T라고 하고 Pattern의 길이를 P라고할 때 O(T * P)의 시간을 갖게 된다.

하지만 KMP알고리즘으로 구현을 하게되면 O(T + P)의 시간 복잡도를 갖게 된다. 

지금부터 그 알고리즘에 대해 제가 이해한 방식대로 설명하도록 하겠다.

KMP알고리즘의 원리는 "비교한 정보의 최대한의 활용"이다. 백준저지에서 제공한 예시를 보도록 하자.

"ABC ABCDAB ABCDABCDABDE"라는 Text에서 "ABCDABD"라는 Pattern을 찾아야 한다. 띄어쓰기도 하나의 문자열로 간주하자.

일반적인 방식은 위에서 설명을 했으니 아래 간단하게 설명을 하도록 하겠다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
Text	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
	0	1	2	3	4	5	6
Pattern	A	B	C	D	A	B	D

일방적인 방식으로는 Text[0]부터 Text[6]까지와 Pattern[0]부터 Pattern[6]까지가 일치하지 않기 때문에 

아래와 같이 다시 비교를 시작한다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
Text	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
		0	1	2	3	4	5	6
Pattern		A	B	C	D	A	B	D

하지만 KMP알고리즘의 원칙 "비교한 정보의 최대한의 활용"에 의거하면

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
Text	A	B	C		A	B	C	D	A	B		A	B	C	D	A	B	C	D	A	B	D	E
	0	1	2	3	4	5	6
Pattern	A	B	C	D	A	B	D

위 표의 루비색으로 칠해진 정보를 낭비하지 말자 라는게 KMP 알고리즘의 핵심이라고 할 수 있다.

KMP알고리즘에서 "비교한 정보의 최대한의 활용"을 위해 KMP를 적용하기(?)에 앞서

접두사와 접미사에 대해 알아야 한다.

문자열 "ABAABAB"의 접두사는 아래와 같다.

"A"

"AB"

"ABA"

"ABAA"

"ABAAB"

"ABAABA"

"ABAABAB"

→ 총 7개

그렇다면 문자열 "ABAABAB"의 접미사는 금방 눈치를 챌 수 있을 것이다.

"B"

"AB"

"BAB"

"ABAB"

"AABAB"

"BAABAB"

"ABAABAB"

→ 총 7개

여기서 우리가 알아야할 정보는 당연히 접두가사 뭔지 접미사가 뭔지가 아니라 

"크기가 7인 문자열 "ABAABAB"에 대해 인덱스 0부터 6까지의 부분 문자열 중 

자기 자신의 문자열을 제외 하고 접두사와 접미사가 같은 문자열 중

가장 긴 것의 길이"

를 알아야 한다. 무슨 말인지 글로는 전혀 이해가 안 된다.

그렇다면 바로 문자열 "ABAABAB"를 위 문장에 대한 예시로 제시하겠다.

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

이해가 되는가? 아마 표를 보면 다른 부연 설명 없이 한번에 이해가 될 것이다.(cf. 파란색 == 빨강색인 문자열의 최대 길이)

그리고 우리가 구하고자 하는 "길이"는 위 표에서 배경을 루비색으로 색칠한 값이다.  

한번 더 "AABAA"의 예시를 보도록 하자.

	부분 문자열
0	A	0
1	AA	1
2	AAB	0
3	AABA	1
4	AABAA	2

확실하게 이해가 될 것이다.

그러면 "AAAAA"는 어떻게 값들이 나올까?

	부분 문자열
0	A	0
1	AA	1
2	AAA	1
3	AAAA	2
4	AAAAA	2

이런 식으로 값이 나왔는가? 그렇다면 잘못 이해하고 있는 것이다.

사실 백준저지의 "찾기" 알고리즘과 "광고"(https://www.acmicpc.net/problem/1305)알고리즘을 같이 풀고 있었다.

광고 문제를 풀면서 내가 위 예시들을 잘못 이해하고 있다는 것을 알게 되었는데

"크기가 7인 문자열 "ABAABAB"에 대해 인덱스 0부터 6까지의 부분 문자열 중 

자기 자신의 문자열을 제외 하고 접두사와 접미사가 같은 문자열 중

가장 긴 것의 길이"

여기서 "인덱스 0부터 6까지의 부분 문자열", "자기 자신의 문자열을 제외 하고 접두사와 접미사가 같은 문자열"

이부분을 유심하게 볼 필요가 있다. 

언어적인 분석보다 그냥 바로 예시로 설명하겠다.

첫 예시 문자열 "ABAABAB"를 보면 

인덱스 0인 문자열("A")은 "접두사와 접미사가 자기 자신이기 때문에 값은 0"

인덱스 1인 문자열("AB")은 

접두사가 "A", "AB"

접미사가 "B", "AB"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 없기 때문에 0"

인덱스 2인 문자열("ABA")은

접두사가 "A", "AB", "ABA"

접미사가 "A", "BA", "ABA"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 "A"이기 때문에 그것의 길이가 1"

인덱스 3인 문자열("ABAA")은

접두사가 "A", "AB", "ABA", "ABAA"

접미사가 "A", "AA", "BAA", "ABAA"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 "A"이기 때문에 그것의 길이가 1"

인덱스 4인 문자열("ABAAB")은

접두사가 "A", "AB", "ABA", "ABAA", "ABAAB"

접미사가 "B", "AB", "AAB", "BAAB", "ABAAB"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 "AB"이기 때문에 그것의 길이가 2"

이하 생략 ... ... 

이런식으로 해서 사실 아래의 표가 완성이 된 것이다.

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

그럼 위 방식으로 "AAAAA"를 적용해 보자.

인덱스 0인 문자열("A")은 "접두사와 접미사가 자기 자신이기 때문에 값은 0"

인덱스 1인 문자열("AA")은

접두사가 "A", "AA"

접미사가 "A", "AA"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 "A"이기 때문에 그것의 길이가 1"

인덱스 2인 문자열("AAA")은

접두사가 "A", "AA", "AAA"

접미사가 "A", "AA", "AAA"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 "A", "AA"인데 그 중 최대 길이는 "AA"이므로 2"

인덱스 3인 문자열("AAAA")은

접두사가 "A", "AA", "AAA", "AAAA"

접미사가 "A", "AA", "AAA", "AAAA"

"자기 자신의 문자열을 제외한 접두사와 접미사가 같은 것이 "A", "AA", "AAA"인데 그 중 최대 길이는 "AAA"이므로 3"

이하 생략... ...

이런식으로 아래 표가 완성될 것이다.

	부분 문자열
0	A	0
1	AA	1
2	AAA	2
3	AAAA	3
4	AAAAA	4

여기까지가 KMP 알고리즘을 들어가기 위한 선행 지식이다.

사실 위 배열을 구하는 알고리즘을 구현할 수 있다면 KMP 알고리즘 또한 바로 구현이 가능하다.

위 배열을 구하는 방법과 KMP 알고리즘을 구현하는 방법이 정말 비슷하다 못해 똑같기 때문이다.

때문에 먼저 위 배열을 구현하는 방법에 대해 설명을 한 뒤에 KMP 알고리즘에 대해 설명 및 구현을 하겠다.

경험상 이 방법을 먼저 알고 KMP 알고리즘 구현을 접하면 엄청 쉽게 느껴질 것을 알기에 조금만 참고 따라오자.

자 그럼 문자열 “BCBCBCA”에 대해

“문자열의 인덱스 0부터 6까지 중 접두사와 접미사가 같은 최대 길이 – Pattern에 대한 배열”를 코드 상으로 구하는 로직을 세워보자.

 

우리는 각 인덱스마다 “접두사와 접미사가 같은 것들 중 최대 길이”를 구해야하므로 길이가 “BCBCBCA”만큼의 배열이 필요하다.

그 배열의 이름을 Pattern에 대한 i이므로

int pi[7]

라고 선언할 수 있다.

 

인덱스 i=0 일 때,

pi[0]=0이 된다.(cf. 위에서 충분히 설명했으니 이유는 설명하지 않겠다.)

 

인덱스 i=1 일 때,

우리는 인덱스가 1일 때, “BC”의 “접두사와 접미사가 같은 것들 중 최대 길이”를 구해야 한다.

“BC”의 접두사는

“B”, “BC”이고,

접미사는

“C”, “BC”이다.

접두사 “B”와 접미사 “C”를 비교하게 된다. 그래서 같은 것이 더 이상 없으니 길이는 0이 된다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
		0	1	2	3	4	5	6
p		B	C	B	C	B	C	A

자 그럼 위 표를 보자. 루비색으로 칠한 pattern[1]과 pattern[0]을 비교하는 것이 보일 것이다.

즉, pi[1]=0; 이 되는 것이다.

어느 정도 인정이 되면, 인덱스 i=2일 때를 보자.

인덱스 i=2 일 때,

우리는 인덱스가 2일 때, “BCB”의 “접두사와 접미사가 같은 것들 중 최대 길이”를 구해야 한다.

“BCB”의 접두사는

“B”, “BC”, “BCB”이고,

접미사는

“B”, “CB”, “BCB”이다.

접두사 “B”와 접미사 “B”를 비교하고, “BC”와 “CB”를 비교한다. 그래서 길이가 1이 된다.

근데 여기서 중요한 점이 있다. 바로 “BC”와 “CB”를 비교하지 않아도 된다는 점이다. 바로 이점에 KMP알고리즘의 핵심 원리가 들어간다. 인덱스가 1일 때 우린 이미 위 내용을 비교를 한 적이 있다. 언제 비교를 했냐고 의문이 생길 것이다. 바로 접두사 “BC”의 “B”와 접미사 “CB”의 “C”를 인덱스가 1일 때 비교를 하지 않았는가? 우리는 “접두사와 접미사가 같은 최대 길이”를 구하고 있다. 그렇다면 첫 문자열이 다르다는 것은 그 뒤의 문자열을 비교할 가치도 없게 되는 것이다.

자 그럼 다음 아래 표를 통해 위 내용을 다시 설명하겠다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
		0	1	2	3	4	5	6
p		B	C	B	C	B	C	A

자 위 표는 접두사 “BC”와 접미사 “CB”를 비교하는 표이다. 하지만 우리는 이미 인덱스 1일 때, pattern[0]과 pattern[1]을 비교한 적이 있다(진한 루비색). 그렇기 때문에 위 표는 비교할 필요가 없다는 것을 인정할 수 있을 것이다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

자 위 표는 접두사 “B”와 접미사 “B”를 비교하는 표이다. 즉 pattern[0]과 pattern[2]의 비교를 통해 pi[2]=1이 된다.

 

인덱스 i=3 일 때,

우리는 인덱스가 3일 때, “BCBC”의 “접두사와 접미사가 같은 것들 중 최대 길이”를 구해야 한다.

“BCBC”의 접두사는

“B”, “BC”, “BCB”, “BCBC”이고,

접미사는

“C”, “BC”, “CBC”, “BCBC”이다.

접두사 “B”와 접미사 “C”를 비교하고, “BC”와 “BC”를 비교하고, “BCB”와 “BCB”를 비교한다. 그래서 길이가 2이 된다.

자 위의 내용을 바로 이했다면 한 번에 알 수 있을 것이다. 우리가 비교를 하지 않아도 되는 것은 어떤 것이 있을까?

“BCB”와 “CBC”를 비교하지 않아도 된다는 것은 분명 알 수 있다. (cf. 인덱스가 1일 때 “BCB”의 “B”와 “CBC”의 “C”를 비교 함)

그리고 접두사 “BC”의 “B”와 접미사 “BC”의 “B”를 비교하지 않아도 된다. 마찬가지로 인덱스가 2일 때 이미 접두사 “BC”의 “B”와 접미사 “BC”의 “B”를 비교했기 때문이다.

그리고 “B”와 “C”는 같든 다르든 간에 비교할 필요가 없다. 왜냐하면 우리는 “최대 길이”를 구해야 되기 때문이다!!

자 그럼 다음 아래 표를 통해 위 내용을 다시 설명하겠다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
		0	1	2	3	4	5	6
p		B	C	B	C	B	C	A

자 위 표는 접두사 “BCB”와 접미사 “CBC”를 비교하는 표이다. 하지만 우리는 이미 인덱스 1일 때, pattern[0]과 pattern[1]을 비교한 적이 있다. 그렇기 때문에 위 표는 비교할 필요가 없다는 것을 인정할 수 있을 것이다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

자 위 표는 접두사 “BC”와 접미사 “BC”를 비교하는 표이다. 하지만 우리는 이미 인덱스 2일 때, pattern[0]과 pattern[2]를 비교한 적이 있기 때문에 pattern[1]과 pattern[3]만을 비교하면 된다. 즉, pi[3]=2; 가 된다

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
				0	1	2	3	4	5	6
p				B	C	B	C	B	C	A

그리고 마지막으로 pattern[0]과 pattern[3]은 비교할 필요가 없다. 이유는 이미 설명했으니 넘어가도록 하자.

 

이제 어느 정도 패턴이 눈에 들어올 것이다.

인덱스 i=4일 때,

우리는 인덱스가 3일 때, “BCBCB”의 “접두사와 접미사가 같은 것들 중 최대 길이”를 구해야 한다.

“BCBCB”의 접두사는

“B”, “BC”, “BCB”, “BCBC”, “BCBCB”이고,

접미사는

“B”, “CB”, “BCB”, “CBCB”, “BCBCB”이다.

접두사 “B”와 접미사 “C”를 비교하고, “BC”와 “BC”를 비교하고, “BCB”와 “BCB”를 비교한고, “BCBC”와 “CBCB”를 비교한다. 그래서 길이가 3이 된다.

위에서 충분한 설명이 되었을 것이라 믿고 표만으로 설명을 대신하겠다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
		0	1	2	3	4	5	6
p		B	C	B	C	B	C	A

위 표는 접두사 “BCBC”와 접미사 “BCBC”를 비교하는 표이다. 하지만 우리는 이미 인덱스 1일 때, pattern[0]과 pattern[1]을 비교한 적이 있다. 

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

위 표는 접두사 “BCB”와 접미사 “BCB”를 비교하는 표이다. 하지만 우리는 이미 인덱스 2일 때, pattern[0]과 pattern[2]를 비교한 적이 있고, 인덱스 3일 때, pattern[1]과 pattern[3]을 비교한 적이 있기 때문에 pattern[4]과 pattern[2]만을 비교하면 된다. 즉, pi[4]=3; 이 된다.

그 이후는 비교할 필요가 없다 그 이유가 명확하지 않다면 윗부분을 다시 정독하기를 바란다.

 

인덱스 i=5 일 때,

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

위 표는 접두사 “BCBC”와 접미사 “BCBC”를 비교하는 표이다. 하지만 우리는 이미 인덱스 2일 때, pattern[0]과 pattern[2]를 비교한 적이 있고, 인덱스 3일 때, pattern[1]과 pattern[3]을 비교한 적이 있고, 인덱스 4일 때, pattern[4]과 pattern[2]를 비교한 적이 있기 때문에 pattern[5]과 pattern[3]만을 비교하면 된다. 즉, pi[5]=4; 가 된다.

 

인덱스 i=6 일 때,

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

위 표는 접두사 “BCBCB”와 접미사 “BCBCA”를 비교하는 표이다. 하지만 우리는 이미 인덱스 2일 때, pattern[0]과 pattern[2]를 비교한 적이 있고, 인덱스 3일 때, pattern[1]과 pattern[3]을 비교한 적이 있고, 인덱스 4일 때, pattern[4]과 pattern[2]를 비교한 적이 있고, 인덱스 5일 때, pattern[5]과 pattern[3]를 비교한 적이 있기 때문에 pattern[6]과 pattern[4]만을 비교하면 된다.

 

그런데 여기서 pattern[6]과 pattern[4]가 다르다는 것을 알았다. 그럼 어떻게 해야 될까? 그렇다! KMP 알고리즘의 원리에 맞게 앞의 정보를 활용하는 것이다. 지금까지 우리가 이해했던 것들이 빛을 바래는 순간이다.

 

지금까지의 pattern배열을 정리해보면

pi[0] = 0

pi[1] = 0

pi[2] = 1

pi[3] = 2

pi[4] = 3

pi[5] = 4

이렇게 된다. 위 값들은 접두사와 접미사가 같은 것들 중 최대 길이를 나타내고 있다. 그렇다는 것은 접두사와 접미사가 같기 때문에 일치되는 것만큼 이동이 가능하다는 것을 뜻한다. 즉, 접두사와 접미사가 같은 것을 활용해서 접두사의 위치를 접미사의 위치로 이동시키는 것이다!!

 

자 표로 설명을 하겠다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

현재 pattern[4]와 pattern[6]이 다른 것까지 우리는 알고 있다.

원래 일반적이 방법이라면! 

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
				0	1	2	3	4	5	6
p				B	C	B	C	B	C	A

pattern[4]와 pattern[6]이 다르기 때문에 한 칸 옮겨지는 것을 생각할 수 있을 것이다. 위 표처럼 말이다.

그러나!! 우리는 접두사와 접미사가 같은 최대 길이를 알고 있기 때문에! 다시 말해서 접두사를 접미사로 옮긴다면?! 그렇다면 이전 정보를 충분히 활용할 수 있다고 말할 수 있다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
					0	1	2	3	4	5	6
p					B	C	B	C	B	C	A

위 표처럼 말이다! 즉 다시 말해서 우리는 pi[3]의 정보를 활용해서 “BCBC”의 최대 접두사는 “BC”이고 최대 접미사는 “BC”인 것을 알고 있다. 그럼 접두사의 “BC”위치를 접미사의 “BC”에 일치시키면 위 표처럼 이동된 것이 이해가 될 것이다.

자 다시 정리해서 말을 하자면!

우리는 pattern[4]와 pattern[6]을 비교할 때 다르다는 것을 알았고, pattern[4]비교 대상 이전의 값인 pi[3]의 정보를 활용해서 비교 대상의 위치를 이동시켰다.

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
					0	1	2	3	4	5	6
p					B	C	B	C	B	C	A

그리고 우리는 다시 pattern[2]와 pattern[6]을 비교할 수 있다! pattern[2]와 pattern[6]의 비교를 통해 또 같지 않다는 것을 알게 되었고 pattern[2] 바로 이전 정보인 pi[1]의 값을 활용해 비교 대상을 옮길 수 있다.

pi[1]=0; 이므로 최대 접두사와 접미사가 같은 것이 없다는 것을 확인할 수 있다. pi[]의 값이 0이라는 것은 접두사와 접미사가 같은 것이 없다는 것을 의미할 수 있지만, 그 구간에 더 이상 같은 것이 없다는 것을 의미한다. 만약 같은 것이 있었다면 분명 pi의 값이 0이 나올 리가 없다. 그렇게 되면 그냥 비교 대상을 처음으로 돌리면 된다. 다음의 표처럼 말이다!

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
							0	1	2	3	4	5	6
p							B	C	B	C	B	C	A

또 다시 같지 않으니 pattern[0]의 이전 값이 없으므로 pi[6]=0; 으로 초기화하면 된다.

 

자 표로 한눈에 비교 패턴을 보도록 하자!

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
		0	1	2	3	4	5	6
p		B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
			0	1	2	3	4	5	6
p			B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
					0	1	2	3	4	5	6
p					B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
							0	1	2	3	4	5	6
p							B	C	B	C	B	C	A

	0	1	2	3	4	5	6
p	B	C	B	C	B	C	A
								0	1	2	3	4	5	6
p								B	C	B	C	B	C	A

pi배열을 구하는 것의 충분한 설명이 되었을 것이라 생각한다.

 

 

위 내용을 충분하게 이해했다면 KMP알고리즘은 금방 이해가 가능하다.

Text 문자열 “BCBCBCCBCBCBCD”에서 Pattern 문자열 “BCBCBCD”를 KMP알고리즘으로 풀어보자.

KMP 알고리즘을 적용하기 위해서 먼저 Pattern에 대한 Pi배열을 구하는 것이 우선이다.

그럼 Pattern의 문자열 “BCBCBCD”의 Pi배열을 위 방식으로 구했다고 생각하고 시작하도록 하겠다.

 

Pi[7] = {0, 0, 1, 2, 3, 4, 0} 이다.

 

위 예시처럼 비교했던 문자열은 진한 루비색으로, 비교 중인 문자열은 연한 루비색으로 표현하겠다.

 

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
	0	1	2	3	4	5	6
P	B	C	B	C	B	C	D

여기서 Text[6]과 pattern[6]이 서로 다르다. 우리는 Pi배열의 정보를 이용해서 이미 알고 있는 정보를 충분히 활용할 수 있다.

Pattern 문자열의 0부터 5까지의 인덱스가 Text 문자열의 0부터 5까지의 인덱스가 서로 일치함을 알고 있다. 그렇다면 pi[5]를 이용해서 접두사와 접미사를 일치시킬 수 있을 것이다.

pi[5] = 4임을 알고 있기 때문에 다음과 같이 이동할 수 있다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
			0	1	2	3	4	5	6
P			B	C	B	C	B	C	D

위 표는 pattern의 접두사 “BCBC”를 Text의 접미사 “BCBC”에 일치시킨 것이다. 그리고 Text[6]과 Pattern[4]를 비교하게 되고 다르다는 것을 알았기 때문에 pi[3]의 정보를 활용해서 다음과 같이 이동시킬 수 있다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
					0	1	2	3	4	5	6
P					B	C	B	C	B	C	D

이후 방식은 여러 번 설명을 했으니 표로 대신하겠다. 다시 말하지만 pi[]의 값이 0이라는 것은 그 구간에 같은 것이 없다는 것이다!!

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
							0	1	2	3	4	5	6
P							B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	B	C	B	C	B	C	C	B	C	B	C	B	C	D
								0	1	2	3	4	5	6
P								B	C	B	C	B	C	D

분명 다음 표가 한 번에 이해가 될 것이라 믿어 의심하지 않는다.

만약 이해가 되지 않는다면 pi 배열 구하는 방법을 다시 한번 정독하기를 바란다.

 

다음은 위 방식대로 코딩을 해봤다.

위 방식을 제대로 이해했다면 아래코드를 하나씩 하나씩 따라가보면

충분히 코드도 이해가 될 것이다.

기회가 되면 코드 리뷰도 추가하도록 하겠다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int * getPi(string p) {
	int len_p = (int)p.size();
	int * pi = new int[len_p];
	pi[0] = 0; 
	int j = 0;
	for (int i = 1; i < (int)p.size(); i++) {
		while (p[i] != p[j]) {
			if (j == 0) {
				pi[i] = j;
				break;
			}
			j = pi[j - 1];
		}
		if (p[i] == p[j])
			pi[i] = ++j;
	}
	return pi;
}

vector<int> kmp(string t, string p, int * pi) {
	vector<int> v;
	int j = 0, len_p = (int)p.size(), len_t = (int)t.size();
	for (int i = 0; i < len_t; i++) {
		while (t[i] != p[j]) {
			if (j == 0)
				break;
			j = pi[j - 1];
		}
		if (t[i] == p[j]) {
			j++;
			if (j == len_p) {
				v.push_back(i - len_p + 2);
				j = pi[j - 1];
			}
		}
	}
	return v;
}

int main(void) {

	string text;
	string pattern;
	vector<int> v;

	getline(cin, text);
	getline(cin, pattern);

	int * pi = getPi(pattern);
	
	v = kmp(text, pattern, pi);

	cout << (int)v.size() << endl;
	for (vector<int>::size_type i = 0; i < v.size(); i++) 
		cout << v[i] << " ";
	
	return 0;
}