kmp

KMP 알고리즘

KMP 알고리즘에 대해 공부하다가 헷갈리는 것들이 있어 자세히 정리했다. 책을 참고했음을 밝힌다. 먼저, KMP 알고리즘이란 문자열 검색을 보다 효율적으로 실행하는 알고리즘으로, 전체 문자열의 모든 부분에서 문자열 비교를 행하지 않으면서 대상 문자열을 빠르게 검색해 낸다. 전체 문자열이 짧으면 몰라도, 수천 수만 줄로 이루어진 문서에서 단어를 검색하는 작업은 모든 글자에서 하나하나 단어를 확인하기에는 무리가 있을 수 있다. 그래서 우리는 naive한 방법보다 훨씬 효율적인 KMP 알고리즘을 사용한다. 가장 간단한 알고리즘부터 떠올려 보자 먼저, 우리가 문자열 검색을 수행하고자 하는 전체 문자열을 '짚더미(haystack)', 그리고 찾아내고자 하는 대상 문자열을 '바늘(needle)'이라고 칭하자. 짚더..