KMP 알고리즘

1. KMP 알고리즘

패턴을 문장 안에서 좌에서 우로 비교하는 것. 브루트-포스 알고리즘과 다르게 패턴의 위치를 좀더 효율적으로 이동시킨다. 패턴과 문장의 불일치가 발생했을 때 중복연산을 최대한 피하면서 패턴을 우측으로 이동시킨다. 이를 위해서는 문장의 불일치 발생 시, 얼마만큼 건너 뚜니 후에 비교연산을 할 것인가를 판단하여야 한다.

 

2. 실패함수(파이 배열)

KMP 알고리즘에서 탐색 문자열의 접두사와 접미사의 일치 부분을 계산하여 배열의 형태로 저장하는 함수

i는 접미사 가리키는 인덱스, len은 접두사 가리키는 인덱스

7번째 : 6번째에 len=2, i=5일 때, A가 이미 일치했던 사실을 알기 때문에 이를 이용하기 위해 len은 lps[len-1]로 이동하는 것. 이는 KMP 알고리즘 원리와 동일하다.

노란색=일치했을 때

KMP 알고리즘에서는 일치했을 때에도, 불일치했을 때와 마찬가지로 그 전까지는 일치했다는 것을 이용해 몇 글자 건너서 검사를 다시 시작한다. 

 

3. 시간 복잡도

탐색을 접두, 접미사의 길이를 이용하여 건너뛰므로, 문자열의 길이에 비례한다.

원본 문자열의 길이가 N, 탐색 문자열의 길이가 M이라면 최종적인 시간 복잡도는 O(N+M)이다.