7장 문자열 검색

문자열 검색이란?

어떤 문자열안에 다른 문자열이 있는지 검사하고 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다.

1. 브루트 포스법

선형 검색을 단순하게 확장한 알고리즘이라 단순법이라고 한다.

원리

만약 텍스트 apple에서 패턴 ple을 검색하는 방법이다.
첫번째 시작부분인 a에서부터 패턴의 총 개수인 3개를 검사한다.
다르다면 한칸 이동하여 반복 수행한다.
만약 패턴이 모두 맞다면 시작하는 인덱스를 출력하며 종료한다.

2. KMP법

브루트 포스법은 틀린 패턴이 있으면 한칸만 이동하고 다시 검색을 한다.
하지만 KMP법은 버리지 않고 활용하는 알고리즘이다.

원리

버리지 않고 활용을 하지만 몇번째 문자열부터 다시 검사를 할지 판단하는 표를 만들어 재활용이 가능하다는 장점이 있으나 보이어 무어법보다 느리며 복잡하다.

3.보이어 무어법

KMP법보다 더 효율적고 실제로 많이 사용하는 알고리즘이다.
패턴의 끝문자에서 시작하여 앞쪽을 향해 검사를 수행한다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다.

원리

만약 패턴이 "ABAC"일 때, 표는 다음과 같이 결정한다.

1. 패턴에 포함되지 않는 문자를 만난 경우
   패턴 이동량은 곧 n이다. 패턴의 문자의 개수인 4만큼 이동한다.
2. 패턴에 포함되는 문자를 만난 경우
   마지막에 나오는 위치의 인덱스가 k이면 이동량은 n-k-1이다.
   같은 문자가 패턴 안에서 중복해서 존재하지 않으면 패턴의 끝 문자의 이동량은 n이다.

참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편