kmp
-
[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘Development/Algorithm 2020. 5. 4. 05:20
다룰 내용 Brute-Force로 패턴 매칭 KMP 알고리즘이란 무엇인가? KMP 알고리즘 구현 Brute-Force로 패턴 매칭 기존에 있는 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴과 일치하는지 일일이 확인하는 방식으로 동작하게 됩니다. 기존 문자열을 패턴 길이만큼 비교해보기 때문에 시간 복잡도는 O(문자열 길이 * 패턴 길이)가 됩니다. 위의 그림처럼 하나 하나 일치하는지 비교를 하기 때문에 문자열의 길이가 길어진다면 비효율적인 탐색이 됩니다. KMP 알고리즘이란 무엇인가? 불일치가 발생한 텍스트 문자열의 앞부분에 어떤 문자가 있는지 미리 알고 있기 때문에 불일치가 발생한 앞부분에 대해서 다시 비교하지 않으면서 매칭이 일어나는지 판단할 수 있는 알고리즘입니다. 시간 복잡도는 O(문자열 길이 ..