KMP 알고리즘(Knuth-Morris-Pratt Algorithm)은 문자열 검색 알고리즘으로, 주어진 텍스트 내에서 패턴을 효율적으로 찾는 데 사용된다. 이 알고리즘은 1977년 컴퓨터 과학자인 도널드 크누스(Donald Knuth), 빌 모리스(Bruce Morris), 그리고 엘리어트 프랫(Elliot Pratt)의 이름을 따서 명명되었다.

KMP 알고리즘은 패턴을 텍스트에 순차적으로 비교하여 검색하는 전통적인 방법과 달리, 반복되는 문자의 비교를 피하기 위해 미리 처리된 정보를 활용한다. 이 알고리즘은 두 단계로 구성된다. 첫 번째 단계는 패턴에 대한 부분 일치 테이블(partial match table)을 생성하는 것으로, 이 테이블은 패턴 내에서 접두사와 접미사가 일치하는 길이를 저장한다. 두 번째 단계에서는 텍스트에 대해 패턴을 검색하는 과정에서 이 정보를 이용하여 불필요한 비교를 줄인다.

KMP 알고리즘의 시간 복잡도는 O(n + m)이며, 여기서 n은 텍스트의 길이, m은 패턴의 길이이다. 이 효율성 덕분에 KMP 알고리즘은 대규모 데이터에서 패턴을 찾는 데 널리 사용되며, 컴파일러, 텍스트 편집기 및 데이터 검색 시스템 등 다양한 분야에서 응용된다.