문자열 검색

1. 브루트-포스법

선형 검색을 확장한 알고리즘이므로 단순법, 소박법이라고 한다.

이미 검사를 진행한 위치를 기억하지 못하므로 효율은 떨어진다.

2. KMP법

(D.E. Knuth, V.R. Pratt, J.H. Morris)

다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 Brute-Force법과 다르게 중간 결과를 효율적으로 사용하는 알고리즘

Text와 Pattern의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함

패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임

KMP법 : 건너뛰기표 만들기

: 몇 번째 문자부터 다시 검색할지’에 대한 값을 미리 저장하는 표

KMP법 성능

Brute-Force법보다 복잡
Boyer-Moore법과는 성능이 같거나 좋지 않아 실제 프로그램에서 거의 사용하지 않는다.

3. Boyer-Moore 법

Boyer-Moore법은 Brute-Force법을 개선한 KMP법보다 효율이 우수하여 실제 문자열 검색에 널리 사용하는 알고리즘

R.S. Boyer & J.S. Moore, “A Fast String Searching Algorithm,” Communications of the ACM, vol.20(10), Oct. 1977, pp.762-772.

패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 결정함

Boyer-Moore법 : 패턴의 마지막 문자가 다른 경우

Boyer-Moore법 : 패턴의 마지막 문자가 같은 경우

Boyer-Moore법 : 패턴과 텍스트의 문자가 다른 경우

Boyer-Moore법 : 검색에 성공한 경우

Boyer-Moore법 : 건너뛰기표

---

문자열 검색 알고리즘의 시간 복잡도와 실용성

Text의 문자개수 : n
Pattern의 문자개수 : m

Brute-Force법

• 시간복잡도 : O(mn)
• 평균(n)으로 단순하나 실제로 빠르게 동작함

KMP법

• 최악인 경우 : O(n)
• 처리가 복잡하고 패턴 안에 반복이 없으면 효율이 떨어짐.
• 순서화일을 읽어 들이며 검색할 때 많이 사용

Boyer-Moore법

• 3가지 방법 가운데 가장 실용적인 문자열 검색 알고리즘
• 최악인 경우 O(n), 평균적으로 O(n/m)