알고리즘 (1) 썸네일형 리스트형 [문자열 검색] KMP 알고리즘 단순하게 문자열을 찾는 방법을 생각해 보면 한 칸씩 비교해가며 일치하는지 확인하는 방법이 있다. ABABABC에서 ABAB가 몇 번 들어가는지 확인하는 예시이다. ⇒ 일치 ⇒ 불일치 ⇒ 일치 ⇒ 불일치 위와 같은 방식으로 찾게 되면 전체 문자열(len = N)에서 찾고자 하는 문자열(len = M)을 하나씩 비교해야 하므로 $O(NM)$의 시간복잡도를 갖게되어 비효율적인 알고리즘이 된다. 하지만, KMP 알고리즘을 사용하게 되면 시간복잡도가 $O(N+M)$으로 획기적으로 줄어들게 된다. 먼저 KMP 알고리즘을 배우기 전에 접두사와 접미사의 개념에 대해 알아야 한다. 예를 들어, apple의 접두사(prefix)는 a ap app appl apple 접미사(subfix)는 e le ple pple appl.. 이전 1 다음
