23. KMP알고리즘
Knuth-Morris-Pratt Algorithm, 단순비교 문자열 매칭의 비효율성을 보완한 알고리즘으로 탐색알고리즘의 대표적인 알고리즘이다.
단순 문자열 매칭에서 비효율적인 연산량, 특히 모든 경우에 대해 문자열을 비교해야한다는 점에서 단순 문자열 매칭은 사용하지 않는다.
이에 반해 KMP알고리즘은 모든 경우를 비교하지 않아도 문자열 탐색이 가능하다는 점에서 많이 활용되는 알고리즘이다.
23-1. 접두사/접미사
LPS(Longest proper prefix which is also suffix)라고도 하는 substring(부분 문자열) 반복 횟수는 해당 문자가 얼마나 나타났는지와 함께, 해당 문자열의 최초인덱스(0번)에서 해당 문자가 얼마나 반복되었는지 말해준다.
이는 다시 말해 전체 문자열과 LPS를 비교하였을때, 문자열이 불일치되는 지점을 발견한 이전 지점까지는 해당 문자열이 반복적으로 나타났고 더이상 비교하지 않아도 된다는 것을 의미한다.
이 부분은 본 강의링크를 통해 더 자세히 확인할 수 있다.
23-2. LPS를 이용한 KMP알고리즘
비교하고자 하는 문자열에 대해 각 문자가 얼마나 반복되는지 파악하는 LPS를 참조해서 탐색을 하는 횟수를 줄이도록 할 수 있다.
23-3. 참조자료
LPS / KMP
https://devbull.xyz/python-kmp-algorijeumeuro-munjayeol-cajgi/
KMP 알고리즘 원리, 구현하기
https://www.youtube.com/watch?v=UcjK_k5PLHI
