KMP 알고리즘

문자열 매칭 알고리즘은 크게 3가지가 있다.

KMP : 문자열 S가 있을 때, 패턴 P를 찾는 알고리즘

Trie : 문자열 N개가 있을 때, 문자열 S를 찾는 알고리즘

Aho-corasick : 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘

그 중 KMP에 대해 알아보자

 

KMP 알고리즘은 KMP 알고리즘을 만든 Knuth, Morris, Prett의 앞글자를 따서 이름을 붙였다.

KMP 알고리즘에서 알아야 하는 것은

1. 접두사와 접미사

apple을 예시로

<접두사>

a

ap

app

appl

apple

 

<접미사>

e

le

ple

pple

apple

이다.

 

2. pi 배열

pi[i]는 주어진 문자열의 0~i까지의 부분문자열 중 접두사==접미사가 될 수 있는 부분 문자열 중 가장 긴 것의 길이다

이때, 접두사가 0~i까지의 부분 문자열과 같으면 안된다.

 

문자열 ABBAAB를 기준으로 pi배열을 구해보자면 

i	부분 문자열	pi[i]
0	A	0
1	AB	0
2	ABB	0
3	ABBA	1
4	ABBAA	1
5	ABBAAB	2

 

가 됩니다.

 

KMP 알고리즘을 이해하기 위한 기초 지식을 익혔습니다.

 

---

참고 내용 

KMP : 문자열 검색 알고리즘 - 멍멍멍 (tistory.com)

KMP : 문자열 검색 알고리즘

추가 참고

문자열 매칭 알고리즘[3](트라이 & 아호 코라식)[String Searching Algorithm, Trie & Aho-Corasick] (tistory.com)