보이어-무어
-
[Algorithm] - 문자열 매칭 ( 보이어무어 알고리즘 )Algorithm/Algorithm 2022. 4. 27. 02:20
보이어-무어 알고리즘 부르트포스, KMP 알고리즘보다 향상된 알고리즘이며 더 자주 사용된다고 한다. 보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다. 알고리즘 KMP 알고리즘의 개선이 된 알고리즘으로, 시간 복잡도는 최악의 경우 O(N) 평균적인 경우 O(N/M)입니다. 이전에 KMP 알고리즘이 O(N+M)이기 때문에 향상이 이루어졌습니다. KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다. KMP 알고리즘과 같이 건너뛰는 경우를 저장하는 배열(skip_table)을 만들어야 합니다. 이때 배열은 본문 문자열이..