국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 String Matching 문서에서 단어를 빠르게 찾으려면? 문서에서 특정 단어를 검색해서 찾는 경우가 종종 있을텐데 이때 찾으려는 단어를 pattern이라 함 이렇게 문서에서 단어를 찾을 때 빠르게 찾으려면 어떤 방법을 써야할지에 대한 알고리즘임 Problem Definition 입력은 길이 n인 문서 문자열 A, 길이 m인 패턴 문자열 P 가 주어지고 보통 n이 m보다 훨씬 큰 상황임 이때 출력은 패턴 문자열과 일치하는 A의 부분 문자열(sub-string) 위치를 출력하게됨 Naive Algorithm 문서 A의 모든 부분 문자열을 순차적으로 패턴 P에 매치해보는 알고리즘을..
