이미 맞춘 정보를 활용
패턴 앞부분이 맞다가 다음 문자에서 실패하면 그 앞부분 안에 다시 시작할 수 있는 구조가 있는지 살핀다. 텍스트의 처음 위치로 돌아가 모든 비교를 되풀이하는 대신 패턴의 다음 비교 위치를 조정한다.
접두부와 접미부
ABABA에서는 전체보다 짧은 접두부 ABA가 접미부이기도 하다. 이런 중첩 정보를 실패 함수나 접두 함수 형태로 저장할 수 있다. 테이블의 정의와 번호 규칙에 따라 저장 값의 표현은 달라진다.
전처리와 검색 비용
대표적인 실패 함수 구현은 패턴 전처리에 O(m), 텍스트 검색에 O(n)이 걸려 전체 O(n+m)이다. 패턴 정보를 보관하는 공간은 O(m)이다. 패턴이 바뀌면 그에 맞는 정보를 다시 만들어야 한다.
적용 범위
KMP는 패턴과 같은 연속 문자열을 찾는다. 오탈자를 허용하거나 중간 문자를 건너뛰는 검색을 자동으로 수행하지 않는다. 모든 일치 위치를 찾을 때는 서로 겹치는 일치도 놓치지 않도록 찾은 뒤의 상태를 이어간다.