KMP(Knuth-Morris-Pratt) 알고리즘에 대한 설명으로 옳… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

KMP는 전처리를 포함해 $O(m+n)$이므로 $O(mn)$이라는 설명이 옳지 않다.
패턴의 실패 함수(접두사·접미사 일치 정보)를 $O(m)$에 미리 만들고, 대상 문자열은 비교 위치를 되돌리지 않고 $O(n)$에 한 번 훑는다. $O(mn)$은 단순 매칭의 최악 복잡도다.
대상과 패턴의 문자를 하나씩 비교하며 매칭 여부를 판단하는 것은 KMP의 기본 동작이다.
매칭 실패 시 미리 만든 실패 함수 값을 이용해 패턴의 비교 재시작 위치를 정한다.
이미 일치한 접두사 정보를 재활용해 불필요한 비교를 건너뛰므로 비교 횟수가 줄어든다.