hellogaon

KMP(Knuth Morris Pratt)는 문자열 검색 알고리즘입니다.길이가 H인 문자열에서 길이가 N인 문자열을 검색하고 싶을 경우완전탐색으로 보게 된다면 시간복잡도가 O(HN)이 되지만KMP는 O(H + N)만에 문자열을 검색하게 해주는 알고리즘입니다.기본적인 원리는 문자열을 검색하다가 일치하지 않는 부분이 나왔을 경우H의 다음 글자와 N의 처음부터 비교하는 것이 아닌지금까지 일치했던 부분의 접미사도 되고 접두사도 되는 문자열의 최대 길이만큼은 또 다시 일치하므로그 길이 이후부터 비교해 나가는 방식입니다.이 때, 접미사도 되고 접두사도 되는 문자열의 최대 길이를 저장해놓은 테이블을부분 일치 테이블이라고 부르는데 이를 구하는 방법 또한N에서 자신을 제외하고 N을 찾는 방법으로 구할 수 있기에비슷한 두..