[알고리즘] 문자열 매칭 알고리즘 - KMP (Knuth-Morris-Pratt) Pattern matching

아래 링크 강의를 수강하고 정리하였습니다. 기초 학습 단계로 부정확한 정보가 있을 수 있습니다. https://youtu.be/yWWbLrV4PZ8 / 나동빈님의 실전 알고리즘 강좌 34강 https://www.youtube.com/watch?v=UcjK_k5PLHI / 코드없는프로그래밍님의 String 강좌 https://youtu.be/GTJr8OvyEVQ / Tushar Roy - KMP Pattern matching 문자열 매칭 알고리즘이란, 특정한 글이 있을 때 그 글안에서 주어진 문자열을 찾는 알고리즘이다. 이전까지 문자열을 찾는 경우에는 브루트포스처럼 O(nm)의 시간을 소요해 문자열을 찾았었다. 이 과정에 KMP 문자열 매칭 알고리즘, 라빈-카프 문자열 매칭 알고리즘을 도입해 매칭에 소요하..

2022.01.20