토픽 35 / 82

KMP 알고리즘 (Knuth-Morris-Pratt)

패턴의 접두사-접미사 정보를 활용하여 불필요한 비교를 건너뛰며 문자열을 효율적으로 매칭하는 알고리즘

목적: 빠른 문자열 매칭, 선형 시간

특징: 전처리(실패 함수), 백트래킹 없음, O(n+m)

핵심: 실패 함수(Failure Function/LPS) - 패턴의 각 위치에서 접두사=접미사 최대 길이

동작: ① 패턴의 실패 함수 계산(O(m)) → ② 텍스트 순회하며 패턴 비교, 불일치 시 실패 함수로 이동(O(n))

시간 복잡도: O(n + m) - n = 텍스트 길이, m = 패턴 길이

공간 복잡도: O(m) - 실패 함수 배열

장점: 선형 시간(O(n+m)), 백트래킹 없음, 효율적

단점: 전처리 필요, 실패 함수 이해 어려움

적용사례: 텍스트 에디터, 검색 엔진, DNA 서열, 로그 분석

비교: KMP(O(n+m)/전처리) vs Naive(O(nm)/단순) vs Rabin-Karp(O(n+m)/해시)

연관: 문자열 매칭, 실패 함수, LPS, 패턴