문자열 검색이란?
- 어떤 문자열 안에 다른 문자열이 포함되어있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것을 칭함
- 검색되는 쪽의 문자열을 텍스트(text), 찾아내는 문자열을 패턴(patton)이라 칭함
- 문자열 검색 알고리즘에서 가장 기초적이고 단순한 방법은 브루트 포스법으로 선형 검색을 단순하게 확장한 알고리즘
- 단점으로는 이미 검사한 위치를 기억하지 못하므로 브푸트 포스법은 효율이 좋지 않음, 즉 일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검색 수행
KMP법이란?
- 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동을 되도록이면 크게 하는 알고리즘
- 몇 번째 문자부터 검사를 다시 시작할지 패턴을 이동할 때마다 계산한다면 좋은 효율을 기대할 수 없으므로 '몇 번째 문자부터 다시 검색할지' 값을 표로 만들어서 문제를 해결
- 예를 들어 패턴의 1~4번째 문자에서 검사를 실패하는 경우에는 패턴을 이동한 뒤 1번째 문자부터 다시 시작해야 하지만 5번째 문자를 검사를 실패하는 경우에 패턴을 이동했을 때 1번째 문자가 일치한다면 2번째 문자부터 검사를 다시 시작함
- KMP법에서 텍스트를 스캔하는 커서 pt는 앞으로 나아갈 뿐 뒤로 돌아오지 않아 브루트 포스법에는 없는 특징을 가짐
- KMP의 단점으로는 알고리즘이 복잡하고 후에 배울 보이어 무어법보다 성능 면에서 같거나 낮은 수준
보이어 무어법이란?
- 패턴의 끝문자에서 시작하여 앞쪽을 향해 검사를 수행하고 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정하는 알고리즘
총정리
- 브루트 포스법의 시간복잡도는 O(mn)이지만 일부러 꾸며 낸 패턴이 아니라면 O(n)으로 단순한 알고리즘이지만 실제로는 아주 빠르게 동작
- KMP법의 시간복잡도는 최악의 경우에도 O(n)이지만 처리하기 복잡하고 패턴 안에 반복이 없으면 효율은 좋지 않다. 하하지만 검색 과정에서 주목하는 곳을 앞으로 되돌릴 필요가 전혀 없으므로 파일을 차례로 읽어 들이면서 검색할 때 사용하면 아주 효율적이다.
- 보이어 무어법의 시간복잡도는 최악의 경우라도 O(n)이고 평균은 O(n/m)이고 배열을 1개가 아니라 2개로 알고리즘을 구현하면 KMP와 마찬가지로 배열을 만드는 데 복잡한 처리 과정이 필요하므로 효율성이 떨어진다.
