[알고리즘] KMP 알고리즘

개념 KMP알고리즘은, 'Knuth-Morris-Pratt' 의 줄임말로써, 전체 문자열에서 특정 문자열(패턴)을 빠르게 찾는 알고리즘이다. 실패함수 가장 기본적으로 생각할 수 있는 O(N^2) 알고리즘이 느린 이유는 문자 하나하나를 다 검색함으로서 효율이 저하되기 때문이다.

이를 극복하기 위해 KMP 알고리즘에서는 실패함수(Fail Function) 라는 개념을 도입했다. 실패함수는 '문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가' 를 알기 위해 사용된다.

즉, '문자 매칭 실패하기 직전 상황에서 접두사/접미사가 일치한 최대 길이' 라고 풀이된다. 예시) 전체 문자열 'ababdababa' 에서 패턴 문자열 'aba..........