알고리즘- KMP 알고리즘, 문자열 검색

KMP를 요약하면 다음과 같습니다.

 

어떤 수의 접미사와 접두사가 일치하는 경우가 있다면 그것을 기억해서 실패시 스킵(다음 탐색때 시작점으로 삼는다)

한다.

 

이를 통해서 굉장히 빠른 탐색이 가능합니다. O(N+M)

 

fail함수를 구현하고 이에 따른 KMP함수를 구현합니다. ( 내용은 비슷합니다.)

 

구현이 익숙치 않아서 해당 부분을 문제를 풀며 좀 연습해봐야할 것 같습니다.

https://www.acmicpc.net/problem/1786

1786번: 찾기