매일 매일 성장하는 섭섭군

KMP Algorithm KMP 알고리즘이란? KMP(Knuth-Morris-Pratt) 알고리즘은 어떤 문자열에서 특정 문자열을 찾고자 할때 유용한 알고리즘입니다. KMP 란 이름이 붙은 이유는 Knuth, Morris, Pratt 세사람이 함께 만들어냈기 때문이라 합니다. KMP 알고리즘을 살펴보기전에 어떤 문자열에서 특정 문자열을 찾고자 한다면 어떻게 해야할까? 단순히 두 문자열을 앞에서부터 차례대로 비교해 나아가면 된다. 효율적이진 않지만 매우 직관적이며 간단합니다. 단순 비교 알고리즘 원본문자열과 찾을 문자열은 다음과 같습니다. 원본 문자열 : "abcdef" 찾을 문자열 : "cd"찾을 문자열이 원본문자열에 있을지 판단하는 과정은 다음과 같이 진행됩니다. 쉽고 단순하게 찾을 수 있지만 O(M*..