1. Introduction Ctrl + F 를 통해 인터넷에서 특정 문자열을 검색할 수 있다. 이런 종류의 검색에 이용되는 문자열 매칭 알고리즘 중 가장 유명한 것이 Knuth-Morris-Pratt(KMP) algorithm이다. 1.1. Navie Method KMP algorithm에 대한 설명을 하기 전 Naive한 문자열 매칭에 관한 이야기를 하겠다. 검색어, 즉 찾고자 하는 문자열을 \(P\)라 하자. 보통 이 \(P\)를 패턴이라고 한다. 우리는 \(P\)를 text \(T\)에서 몇 번 등장하는지, 어디서 등장하는지 알아야 한다. Naive하게 \(P\)를 \(T\)에서 찾으려면 아래의 과정을 수행하게 될 것이다. Naive-String-Matcher(\(T\),\(P\)) 1 \(n =..