Bull

소개만든 사람의 이름 앞 글자를 따서 Knuth, Morris, Prett로 지었다. 해당 알고리즘은 문자열 A에서 문자열 B가 어디에 있는지 찾는 알고리즘이다. 이는 브루트포스를 통해서 모든 경우를 찾아도 되지만, O(NM) 시간복잡도를 가지기 때문에 해당 알고리즘을 사용하면 O(N+M)으로 단축시킬 수 있다.KMP 알고리즘 내에서는 LPS (Logest Prefix which is also Suffix) 알고리즘이 사용되는데, 이는 다른 글로 정리 하였다. [1]에 정리하였다. [1] LPS 정리도 [2] 자료를 통해서 정리를 하였는데, 해당 블로그 글을 작성하신 분이 정리를 참 잘해놓으셔서 이해하는데 큰 도움을 얻었다.원리[1] LPS를 설명할 때 패턴이 일치되는 부분의 접두사와 접미사를 각 문자..