KMP 문자열 매칭 알고리즘

---

오늘은 문자열 찾기 알고리즘인 KMP(Knuth-Morris-Pratt) 알고리즘에 대해서 공부 하겠습니다.

​

​

1. 문자열 매칭(String Matching)

우리들이 흔히들 사용하는 브라우저에서 Ctrl + F(찾기) 기능에서 사용 하는 알고리즘 입니다.

KMP 알고리즘은 "전체 문자열" 과 우리가 찾고자 하는 "패턴 문자열" 이 존재 할때 패턴 문자열을 효율적으로 찾을수 있는 알고리즘 입니다.

​

​

2. KMP 알고리즘 아이디어

먼저 KMP 알고리즘의 핵심 아이디어는 다음과 같은 상황에서 나왔습니다.

위와 같이 전체 문자열 "ababaca" 에서 패턴 문자열 "abac" 를 찾으려는 상황에서

 

패턴 문자열이 2칸을 건너뛰어 찾고자 하는 패턴 인지 검사 할수 있습니다.

 

그 이유는

1) 패턴 문자열의 1번째 문자 "a" 와 패턴 문자열의 3번째 문자 "a" 가 같은 문자이고,

2) 패턴 문자열의 3번째 문자 "a" 와 전체 문자열의 3번째 문자 "a" 문자가 같습니다.

3) 따라서, 패턴 문자열의 1번째 문자 "a" 와 전체 문자열의 3번째 문자 "a" 가 같습니다.

 

이러한 아이디어로 패턴 문자열을 찾고자 할때 우리는 2칸을 건너뛰어 검사를 할 수 있었습니다.

​

따라서, KMP 알고리즘은 패턴 문자열의 접두사(앞글자/prefix), 접미사(뒷글자/suffix) 의 일치 갯수를 미리 파악 하여, 문자열을 검사 할때, 일치 하지 않는 문자를 발견하면, 접두사, 접미사 일치 갯수의 따라 몇 칸을 건너 뛰어 넘어 검사 할수 있어, 패턴 문자열을 찾는 시간을 단축​ 시킬 수 있습니다.

​

​

3. 문자열 순차 탐색

KMP 알고리즘을 사용하지 않고 기존의 문자열 탐색은 아래와 같은 순차 탐색 하는 방법이였습니다. 순차 탐색을 하게되면 전체 문자열과 패턴 문자열 모두를 탐색해야 하기 때문에 최악의 경우 시간 복잡도가 O(M x N) 됩니다.(M은 전체 문자열의 길이, N은 패턴 문자열의 길이) 순차 탐색은 아래와 같은 순서대로 동작 합니다.