KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색을 위한 효율적인 알고리즘이다.

이 알고리즘은 1977년 Donald Knuth와 Vaughan Pratt, 그리고 독립적으로 James H. Morris가 함께 개발한 것이다.

기본 개념

KMP 알고리즘은 문자열 매칭 과정에서 불필요한 비교를 줄이기 위해 패턴의 접두사와 접미사 정보를 활용하는 알고리즘이다.

특징

• 시간 복잡도가 O(N + M)으로, 단순 비교 방식의 O(NM)보다 효율적이다.
• 패턴의 접두사와 접미사 정보를 저장하는 실패 함수(failure function)를 사용한다.
• 문자열 매칭 실패 시 처음부터 다시 비교하지 않고, 이전 비교 결과를 활용한다.

동작 설명

먼저 패턴을 위와 같이 전처리 한다.

KMP 알고리즘의 패턴 전처리는 접두사와 접미사의 일치 정보를 저장하는 과정이다.

전처리 과정의 핵심 단계는 다음과 같다:

1. 실패 함수(failure function) 또는 부분 일치 테이블(partial match table)을 생성한다.
2. 각 위치에서 접두사와 접미사가 일치하는 최대 길이를 계산한다.
3. 계산된 값을 배열에 저장하여 문자열 매칭 시 활용한다.

예를 들어, 패턴 "abaaba"의 전처리 결과는 [0,0,1,1,2,3]이 된다.

이는 각 위치에서:

• a: 이전 일치하는 접두사-접미사 없음 (0)
• b: 이전 일치하는 접두사-접미사 없음 (0)