KMP

KMP는 유명한 문자열 매칭 알고리즘중 하나이다.
찾을 문자열에 대해 회귀할 index를 표시해주는 pi를 이용하여 문자열을 검색한다.
최악의 경우 O(nk)의 시간복잡도를 갖는다. n,k는 각각 찾을 문자열과 검색할 문자열의 길이를 나타낸다.

소스