KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

KMP 알고리즘(Knuth-Morris-Pratt Algorithm)

KMP 알고리즘을 만든 Knuth, Morris, Pratt의 이름 앞 글자를 따서 명명한 알고리즘이다. 우리가 찾고 싶어하는 길이 N의 문자열을 Pattern String으로, Pattern String을 찾을 길이 M의 문자열을 Text String으로 하자. 단순한 Brute Force 문자열 탐색 알고리즘의 시간 복잡도는 O(N*M)인 반면에, KMP 알고리즘의 시간 복잡도는 O(N+M)이다.

1. Brute Force와의 비교

Text String을 "AABABCAABACABC"로, Pattern String을 "ABACABC"라고 할 때 Brute Force로 진행하면 다음과 같은 과정으로 문자열을 탐색한다. Brute Force에서는 Text String에서 처음부터 차례로 Pattern String을 맞추어 보고 다르다면 한 칸 씩 뒤로 밀면서 비교한다.

원본

탐색1

탐색2

탐색3

탐색4

탐색5

탐색6

탐색7

탐색8

반면, 똑같은 예시로 KMP 알고리즘을 사용하면 다음과 같다. Brute Force와 달리, 한 칸 씩 이동하며 비교하는 것이 아니라 접두사와 접미사에 따라 여러 칸을 이동하며 비교를 진행한다. 접두사와 접미사가 일치하는 성질을 활용하면, 접두사를 비교한 이후, 한칸 뒤에 있는 String을 비교하는 것이 아닌 접미사로 바로 넘어갈 수 있다.

원본

탐색1

탐색2

탐색3

탐색4

탐색5

탐색6

예를 들어, 탐색 2에서 Text String에서 "ABA"까지 Pattern String과 일치하는 것을 볼 수 있다. 이떄, "ABA"는 접두사와 접미사가 일치하므로 바로 접미사 "A"로 건너뛰어서 탐색을 시작한다. Brute Force는 탐색 2의 바로 다음 문자인 "B"부터 시작하여 탐색하는 것이지만, KMP 알고리즘은 지금까지 비교한 정보를 활용하여 String의 불필요한 비교 반복을 줄인다.

2. KMP 알고리즘 기본 개념

1) 접두사(Prefix)와 접미사(Suffix)

접두사(Prefix) : 문자열의 왼쪽부터 시작하여 만들 수 있는 부분 문자열
접미사(Suffix) : 문자열의 오른쪽부터 시작하여 만들 수 있는 부분 문자열

접두사와 접미사는 모두 해당 문자열의 전체가 될 수 었으며 문자열 내에서 판단한다. 예를 들어, "YEBAAA"라는 String의 접두사는 "Y", "YE", "YEB", "YEBA", "YEBAA"가 있고, 접미사는 "A", "AA", "AAA", "BAAA", "EBAAA"가 있다.

2) LPS(Longest Prefix which is also Suffix)

LPS는 가장 긴 길이를 가진 접두사인 동시에 접미사인 부분 문자열을 의미한다. 예를 들어, 문자열 "ABABCDAABAB"의 LPS는 "ABAB"이다. LPS는 KMP 알고리즘에서 비교하지 않고 뛰어 넘을 String을 판단하는데 이용된다.

3. KMP 알고리즘 구현

본격적으로 KMP 알고리즘을 구현하기 위해서는 크게 2가지 단계로 이루어진다.

1단계) LPS 테이블 생성
: Pattern String의 LPS에 대한 정보를 구하는 과정이다.

2단계) 이동거리 계산
: LPS를 바탕으로 얼만큼 뛰어 넘을 수 있을지에 대한 이동 거리를 계산하는 과정이다.

3단계) 문자열 비교
: 이동거리를 통해 문자열을 비교하며 Pattern String을 Text String 내에서 탐색하는 과정이다.

1단계. LPS(최대 접두부) 테이블, pi[i] 배열 만들기

Pattern String의 모든 부분 문자열에 대해 LPS를 구하기 위해 문자열의 앞에서부터 하나 씩 문자를 늘려나가는 방식으로 구한다.

아래의 표에서 i와 j는 각각의 알파벳을 가리키는 포인터로 생각하자. i는 LPS를 찾을 문자열의 탐색 중인 문자를 가리킨다. j는 LPS를 찾을 문자열의 맨 앞에서부터 시작하며 다음으로 비교할 접두사 부분에 해당한다.이다. 정리하면, i는 접미사 부분을 판단하고 j는 접두사 부분을 판단한다.

기본적으로 Pattern String의 문자를 하나씩 추가하면서 i를 한 칸씩 뒤로 옮기며 부분 문자열의 LPS에 대해 계산한다. 이후, i와 j가 가리키는 알파벳을 비교한 후 결과에 따라 LPS를 달리 계산한다.

# i와 j가 가리키는 알파벳이 같을 때

: LPS 값으로 j의 Index에 1을 더해주어 적은 후, j를 한 칸 뒤로 옮긴다.

# i와 j가 가리키는 알파벳이 다를 때

: j의 한칸 뒤의 LPS가 가리키는 Index로 이동한 이후, 다시 i와 j를 비교한다.

(j가 0일 때 알파벳이 다르면 LPS 또한 0이다.)

1) "A"

Pattern String	A
Pattern String의 Index	0
j	j
i	i
LPS, pi[i]	0

"A"는 i와 j가 같은 위치의 알파벳을 가리킨다. 이는 하나의 문자로 이루어져 있어서 접두사와 접미사가 존재하지 않는다. 그러므로, LPS는 0이다. 이후, i를 다음 칸의 Pattern String의 알파벳을 가리키도록 옮긴다.

2) "AB"

Pattern String	A	B
Pattern String의 Index	0	1
j	j
i		i
LPS, pi[i]	0	0

"AB"는 i와 j가 다른 종류의 알파벳을 가리킨다. j = 0으로 맨 앞에 존재하므로 다시 LPS 탐색을 시도할 알파벳이 존재하지 않는다. 그러므로 LPS는 0이며 i를 한 칸 뒤로 옮긴다.

3) "ABA"

Pattern String	A	B	A
Pattern String의 Index	0	1	2
j	j
i			i
LPS, pi[i]	0	0	1

"ABA"는 i와 j가 같은 종류의 알파벳을 가리킨다. 현재 Index가 0인 j에 1을 더해주며 LPS는 1이다. 다시 말해, "ABA"까지 보았을 때, 가장 긴 길이의 접두사이면서 접미사는 1이다. 이번에는 i와 j를 함께 다음 칸의 Pattern String의 알파벳을 가리키도록 옮긴다.

4) "ABAC"

Pattern String	A	B	A	C
Pattern String의 Index	0	1	2	3
j		j
i				i
LPS, pi[i]	0	0	1

"ABAC"를 판단하기에 앞서 "ABA"에서 LPS는 1이었다. 마지막 문자 C만을 확인하여 LPS를 결정할 수 있는 이유는 바로 이전의 비교 때문이다. 앞서 "ABA"에서 LPS가 1임을 확인했으므로 길이 1의 접두사와 접미사는 동일하다. 접두사(앞쪽) A의 다음 문자와 접미사(뒤쪽) A의 다음 문자만을 비교하여 같을 경우 LPS 2가 된다.

아쉽게도 접두사 A의 다음 문자인 B와 접미사 A의 다음 문자인 C는 달라 LPS 2가 될 수 없다. 이때 j 이전 알파벳의 LPS 값이 0이므로 j 포인터를 맨 앞 Index 0으로 옮겨준다.

Pattern String	A	B	A	C
Pattern String의 Index	0	1	2	3
j	j
i				i
LPS, pi[i]	0	0	1	0

다시 한번 i와 비교하여도 알파벳이 다르므로 LPS 값에 0을 넣어준다. 이후, i를 한 칸 뒤로 옮겨준다. 두번째로 비교하였을 때 i와 j가 가리키는 알파벳을 비교해서 같았으면 LPS가 1이 되겠지만, 위의 예시에서는 다르므로 LPS는 0이 된다.

5) "ABACA"

Pattern String	A	B	A	C	A
Pattern String의 Index	0	1	2	3	4
j	j
i					i
LPS, pi[i]	0	0	1	0	1

i와 j가 가리키는 알파벳이 "A"로 같다. 그러므로, LPS는 j의 Index에 1을 더해 0+1로 1이다. i와 j를 모두 함께 다음 칸의 Pattern String의 알파벳을 가리키도록 옮긴다. 이는 이전에 찾은 LPS를 활용해 해당 접두사와 접미사의 다음 문자만을 확인하여 "ABACAB"의 LPS를 구하기 위함이다.

6) "ABACAB"

Pattern String	A	B	A	C	A	B
Pattern String의 Index	0	1	2	3	4	5
j		j
i						i
LPS, pi[i]	0	0	1	0	1	2

앞에 "ABAC"와 다르게 접두사 A의 다음 문자인 포인터 j의 B와 접미사 A의 다음 문자인 포인터 i의 B가 같다. 간단히 말해 i와 j가 가리키는 알파벳이 동일하다. 그러므로, "ABACAB"의 LPS는 j의 Index 값에 1을 더해 2이다. "ABACAB"의 가장 긴 접두사이면서 접미사는 "AB"이다. 이후 i와 j를 모두 함께 1칸 씩 뒤로 옮겨준다.

7) "ABACABC"

Pattern String	A	B	A	C	A	B	C
Pattern String의 Index	0	1	2	3	4	5	6
j			j
i							i
LPS, pi[i]	0	0	1	0	1	2

이전에 LPS가 2였으므로 앞서 구한 접두사와 접미사의 다음 문자를 비교해 LPS가 3이 될 수 있는지 확인해보자. 이때, i와 j는 다른 알파벳을 가리키고 있으므로 LPS는 3이 될 수 없다. 동일한 접두사와 접미사를 찾는 데에 실패하였으므로 이제 j를 이동시켜주자. j는 이전 Index의 LPS의 값에 해당하는 Index로 이동한다. 위의 예시에서는 이전 Index인 1의 LPS 값은 0이므로 0번 index의 알파벳으로 j를 이동한다.

Pattern String	A	B	A	C	A	B	C
Pattern String의 Index	0	1	2	3	4	5	6
j	j
i							i
LPS, pi[i]	0	0	1	0	1	2	0

다시 한번 동일하게 i와 j가 가리키는 문자를 비교해보면, 서로 다르다. 즉, LPS는 0이다.

아래의 표는 앞서 구한 최대 접두부 테이블에서 i와 j를 빼서 나타낸 것이다.

Pattern String	A	B	A	C	A	B	C
Pattern String의 Index	0	1	2	3	4	5	6
LPS, pi[i]	0	0	1	0	1	2	0

예를 들어, Pattern String이 "ABACAB" (Index 5까지의 문자열) 일 때 가장 긴 접두사이면서 접미사(LPS)는 2이다. 문자열에서 알 수 있듯이, "AB"가 문장 앞, 뒤로 있는 것을 알 수 있다.

2단계. 이동 거리 계산

최대 접두부 테이블의 LPS의 값에 따라 Text String에서 얼만큼 뛰어넘을지 결정된다. LPS는 Pattern String 내에서 반복되는 부분 문자열임을 확인했으므로 굳이 하나 하나씩 확인하지 않아도 되는 것이다. 다음은 얼마나 뛰어넘을지에 대한 이동 거리에 관한 식이다.

이동 거리 = 일치하는 문자열의 길이 - LPS의 값(pi[i])

Pattern String	A	B	A	C	A	B	C
Pattern String의 Index	0	1	2	3	4	5	6
LPS, pi[i]	0	0	1	0	1	2	0
이동 거리	1-0	2-0	3-1	4-0	5-1	6-2	7-0

위와 동일한 예시에 대해 탐색 2, 3 과정을 보자.

탐색2

탐색3

탐색 2에서 일치하는 문자열의 길이가 "ABA"이므로 3이다. LPS는 "A"로 1이므로 이때의 이동 거리는 3 - 1이 되는 것이다. 우리는 "ABA~"라는 문자열을 찾고 있는데 굳이 한 칸 씩 이동해서 "B"를 확인하는 것이 아니라 접두사와 동일한 부분인 "A"를 찾아 더 많이 이동해서 확인하겠다는 것이다.

3단계. 문자열 비교

이제 이동거리를 이용해서 불필요한 비교를 없애고 Text String 내에서 Pattern Sting을 찾아보자.

탐색 1)

원본

Index

탐색1

Text String의 첫번째 문자 "A"를 비교한다. 첫번째 문자가 일치하므로 다음 문자인 "B"를 이어서 비교해본다. 일치하지 않으므로 비교를 중단한다. 지금까지 일치한 문자열은 "A"이므로 LPS는 0이고 이동 거리는 1이다. 아쉽게도 건너뛸 수 있는 부분이 없으므로 한 칸만 뒤로 이동해서 다시 탐색을 진행한다.

탐색 2)

원본

Index

탐색2

다음으로 Text String의 두번째 문자 "A"부터 탐색해보자. 위의 표에 나타난 것처럼 "ABA"가 일치하지만, Pattern String의 4번째 문자인 "C"에서 다르다. 지금까지 일치한 "ABA"의 Pattern String의 LPS는 1이며 이동 거리는 2이다. 다음 탐색을 진행하기 위해 2만큼 이동하여 "ABA" 접두사 "A"에 있던 자리에서 접미사 "A"의 자리로 2칸 이동하는 것이다.

탐색 3)

원본

Index

탐색3

이어서 탐색을 진행해보면, "AB"까지 Pattern String과 Text String이 일치한다. "AB"의 LPS는 0이고 이동 거리는 2이다. 다음 탐색에서 LPS가 없으므로 일치하는 문자열의 길이인 2만큼 이동한다.

탐색 4)

원본

Index

탐색4

이동한 후에 Pattern String과 Text String에서 일치하는 부분이 없다. 이런 경우에는 Brute Force 방식과 마찬가지로 1칸 만 뒤로 가서 탐색을 진행한다.

탐색 5)

원본

Index

탐색5

이는 1번 탐색과 같은 경우로 일치하는 문자열이 "A" 뿐이고 이동 거리는 1이므로 한 칸만 뒤로 이동한다.

탐색 6)

원본

Index

탐색6

문자를 계속해서 비교하였을 때, 일치하는 문자열이 "ABACABC"로 Pattern String과 동일한 문자열을 찾은 동시에 Text String이 끝났으므로 종료한다. 만약, Text String이 더 남아있었다면, LPS는 0, 이동 거리는 7로 한번에 7칸을 뛰어넘었을 것이다.

위와 같은 과정으로 KMP 알고리즘이 동작한다. 시간 복잡도는 최대 접두부와 이동 거리 테이블 생성에 O(N)을, 문자열을 비교하는데 O(M)의 시간 복잡도가 걸려 총 O(N+M)의 시간 복잡도가 소요된다.

학교에서 강좌를 수강하며 작성한 내용으로 주관적인 내용 및 부족한 부분이 있습니다.

해당 자료에 관한 문의 및 피드백은 연락바랍니다 :]

시간에 따라 더 나은 자료를 위해 수정이 가능합니다!

참고해주세요 😊

'예바의 스터디 > 개념 정리' 카테고리의 다른 글

[컴파일러] FOLLOW(𝞪)의 개념과 예제 (2)	2024.10.13
MLFF(Machine Learning Force Fields)의 개념과 모델 (6)	2024.09.17
[컴파일러] FIRST(𝞪)의 개념과 예제 (2)	2024.09.16
MPNN(Message Passing Neural Network) (4)	2024.08.15

HELLO 예바 :]

KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)