알고리즘 KMP

KMP 실패 함수 점프 구조

불일치가 발생해도 텍스트 포인터를 되돌리지 않고 패턴 포인터만 접두사 정보로 점프합니다.

KMP 처리 단계

string

패턴의 접두사 함수를 미리 계산합니다.

텍스트 포인터는 왼쪽에서 오른쪽으로만 갑니다.

불일치 시 이전 일치 길이를 활용합니다.

패턴 포인터를 prefix table 값으로 이동합니다.

전체 패턴 길이만큼 맞으면 위치를 기록합니다.

prefix table → scan → mismatch → jump → match found

KMP의 장점은 틀렸을 때 어디까지 이미 맞았는지를 기억해 텍스트를 다시 훑지 않는 데 있습니다.