KMP

KMP(Knuth Morris Pratt)는 문자열 검색 알고리즘입니다.

길이가 H인 문자열에서 길이가 N인 문자열을 검색하고 싶을 경우

완전탐색으로 보게 된다면 시간복잡도가 O(HN)이 되지만

KMP는 O(H + N)만에 문자열을 검색하게 해주는 알고리즘입니다.

기본적인 원리는 문자열을 검색하다가 일치하지 않는 부분이 나왔을 경우

H의 다음 글자와 N의 처음부터 비교하는 것이 아닌

지금까지 일치했던 부분의 접미사도 되고 접두사도 되는 문자열의 최대 길이만큼은 또 다시 일치하므로

그 길이 이후부터 비교해 나가는 방식입니다.

이 때, 접미사도 되고 접두사도 되는 문자열의 최대 길이를 저장해놓은 테이블을

부분 일치 테이블이라고 부르는데 이를 구하는 방법 또한

N에서 자신을 제외하고 N을 찾는 방법으로 구할 수 있기에

비슷한 두 개의 함수를 사용하여 KMP를 구현합니다.

KMP 중 부분 일치 테이블만을 응용하여 나오는 문제도 종종 있으며

KMP 원리는 추후 아호코라식 알고리즘을 이해하는 데에도 많은 도움이 됩니다.

기본 문제

1786번: 찾기

1305번: 광고

4354번: 문자열 제곱