문자열 탐색 KMP

N의 길이의 텍스트에서 M의 길이를 가진 패턴을 찾으려고 할 때(N>=M) 일반적인 문자열 탐색 알고리즘. 즉 브루트포스로 모든 문자를 검색한다고 하면 시간복잡도는 O(NM)이 된다. 즉 NM이 1억이 넘어가면 1초 안에 해결할 수 없을뿐더러 텍스트의 길이가 헤아릴 수 없다는 점에서 NM은 매우 비효율적이다. 따라서 해결할 수 있는 방법인 KMP다. KMP는 시간복잡도 O(N)에 해결할 수 있다

 

1. KMP를 구현하기 위해선 패턴의 접두사, 접미사가 같은 최대 길이를 알아야 한다. 이는 KMP에서 점프를 할 때 유용하게 쓰이는 데이터 중 하나다. 보통 이를 실패 배열이라고 부른다.

2. 문자열 탐색 중 어긋나는 경우, 그 전까지는 다 맞다고 할 수 있다. 따라서 맞은 부분 문자열에서 실패 배열을 통해 맞은 부분 문자열은 생략하고, 실패 배열에 있는 값으로 j를 점프할 수 있다

3. 텍스트의 인덱스는 지속적으로 증가하면서, 2번을 수행하기 때문에 O(N)에 해결할 수 있다고 말할 수 있다

 

[참고] https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&referrerCode=0&searchKeyword=KMP

 

[참고] https://bowbowbow.tistory.com/6