Let IT Begin

* Python을 기준으로 합니다문자열 검색 - KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)- 개념KMP (Knuth-Morris-Pratt) 알고리즘 : 불일치가 감지되기 이전까지의 문자열은 다시 비교할 필요가 없다는 점을 활용함이를 통해 $O(NM)$의 time complexity를 가지는 Naive approach에 비해 KMP 알고리즘은 $O(N+M)$의 time complexity로 줄일 수 있음KMP를 위한 문자열 전처리 : 불일치가 발생했을 때 건너뛸 문자 수를 결정하기 위함먼저 건너뛸 문자 수를 결정하기 위해, 패턴 크기 `M`과 동일한 크기의 배열 `lps[]`를 선언함- `lps[]`는 길이가 최대인 접두사(prefix)-접미사(suffix) 배열을 의미이후 ..