KMP(Knuth–Morris–Pratt) 알고리즘은 문자열에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나입니다. 이 알고리즘은 패턴과 문자열을 비교해나가다가 틀렸을 때 틀렸다는 사실보다는 틀리기 전에 일치하는 부분이 있었다는 사실에 집중하는 것이 특징입니다. 그러기 위해서 패턴을 통해서 pi배열을 만들고 패턴과 문자열을 비교해나가면서 pi배열을 통해 다시 비교하는 횟수를 줄이는 과정을 거치게 됩니다. 이제 과정을 하나씩 설명해 보도록 하겠습니다. 이 설명은 백준1786번 : 찾기 문제를 풀면서 작성하였습니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가..