이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열을 검색할 때, 특정 단어를 검색엔진에서 검색할때도 사용될 수 있다. 해당 알고리즘의 시간복잡도는 O(N+M)을 가진다. 구현 KMP 알고리즘은 접두사(prefix)와 접미사(suffix)의 개념을 활용하여 실패함수 테이블을 만들고, 테이블을 활용하여 반복되는 문자열을 건너뛰면서 패턴을 찾는 알고리즘이다. 접두사와 접미사에 대해 간단하게 정리해보고자 예를 들어보겠다. "abacabab"라는 문자열이 있다고 가정하자. 우리는 각 문자의 길이에 따라 접두사와 접미사가 일치하는 최대 길이를 테이블에 저장할 것이다. 실패함수 테이블을..