[Algorithm] - 문자열 알고리즘 (KMP 알고리즘)

문자열 탐색

---

• 문자열을 검색하는 상황은 많은 상황에서 쓰입니다.
• 포털 사이트 키워드 검색에서도 사용될 수 있고, 웹 페이지에서 Ctrl+F 를 눌러서 검색 시 사용될 수 있습니다.
• 본문에서 찾고자 하는 특정한 String을 패턴이라고도 하는데, 이 패턴을 찾는 방법을 패턴 매칭이라고 합니다.
• 문자열 검색이라고 생각하면 됩니다.

 

1. 일반적인 생각 ( Brute-Force )

---

본문 문자열의 길이를 M, 패턴의 길이를 N이라 가정

• 시간 복잡도 : O(NM) 

 

2. KMP 알고리즘(Knuth Morris Partt Algorithm)

---

접두사와 접미사가 같은 부분부터 다시 매칭하면 된다라는 아이디어

• 시간 복잡도 : O( N+M )

1) 접두사( Prefix )

• banana -> b / ba / ban / bana / banan / banana

2) 접미사 ( Suffix )

• banana -> a / na / ana / nana / anana / banana

3) Failure Function

• 문자열에 대해서 prefix == suffix 될 수 있는 부분 문자열 중 가장 긴 것의 길이

AABAA 인 경우

ABAABAB 인 경우

 

• abacab와 매칭되는 문자열을 찾아가는 과정을 그린 것이다.

KMP 알고리즘 이동