Sean :: Dev

KMP (Knuth–Morris–Pratt, 문자열 탐색 알고리즘) 기본적인 문자열 완전탐색 알고리즘에 비해, 약간의 메모리공간을 이용해 불필요한 비교횟수를 줄여 시간복잡도를 줄인다. 예를 들어, samsamsung 문자열에서 samsamsong 문자열을 찾는다면 원래는 0번째 인덱스 s부터 시작하여 쭉 같은지 비교하다가 u가 다르므로 실패하고 이후 1번째 인덱스 a부터 다시 비교하기 시작해, 이땐 처음부터 다르므로 바로 실패, 이후 2번째 인덱스 m부터 ~... 방식으로 비교한다. => 이때 KMP를 사용하면, 맨처음 u가 달라서 실패한 상태에서 samsamsung의 sams와 samsamsong의 sams가 같다는 정보를 기억하고 있다. (물론 결과적으론 비교가 실패하게 되겠지만) 위의 정보를 이용해..