KMP 알고리즘 (패턴 찾기)

시간복잡도 : O(N + M) 

N : 텍스트 길이

M : 패턴(탐색 문자열)의 길이

 

KMP 알고리짐에서 prefix(접두사) suffix(접미사)란?

: 문자열에서 맨앞과 맨 뒤에어서 같은 문자열이 나오는 경우

ex) ABCAB  -> 접두사 : AB, 접미사 : AB

 

핵심 아이디어 : 문자열이 불일치 할 때 앞서 탐색했던 정보를 이용하여 몇 칸 정도는 건너 뛴 후 탐색하겠다!

Simple

비교할 문자열의 인덱스는 계속 증가한다!다만 패턴의 인덱스가 pi 배열의 접두사 접미사가 일치하는 정보를 기반으로 비교하는 패턴의 인덱스가 변하는 것이다.!

이동했을 때 또한 다르면 당시의 pi배열 접두사 접미사의 정보를 가지고 또 건너 뛸 수 있다!

 

건너 뛴 후 preifx와 suffix가 일치해야한다는 전제 조건이 있다.

탐색 문자열의 접두사와 접미사를 미리 알고 있어야지, 얼만큼 건너뛸지 정할 수 있다.