KMP(Knuth-Morris-Pratt) 알고리즘은 두 문자열 s1과 s2가 주어지고, s1가 s2보다 길 때, s1 안에 s2가 포함되어 있는지를 탐색하는 알고리즘입니다. 1. 필요성 가장 기초적으로 브루트 포스를 이용해 s1에 s2가 포함되는 지를 확인하기 위해서는 아래와 같은 단계를 거쳐야 합니다. 2중 반복문을 통해 한 칸씩 옆으로 이동하며 비교를 해야 하기 때문에 시간 복잡도는 O(s1.length * s2.length)가 나오게 됩니다. 이를 개선하기 위해 등장한 알고리즘이 바로 KMP 알고리즘입니다. 위의 사진에서 첫 비교 부분만 분리해서 가져와 보겠습니다. 이미 앞에 세 자리는 같다는 것을 확인했고, 네 번째 자리에서 불일치가 발생했습니다. 그렇다면 '앞에서 이미 연산을 한 세 자리 정보..
