Study Blog

보이어 무어법의 특징이 알고리즘을 고안한 보이어와 무어의 이름을 따서 BM법이라고도 함KMP법보다 효율적이어서 실제 문자열 검색에서 주로 사용패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정함시간복잡도는 최악의 경우라도 O(n)이고 평균 O(n / m)이다. 보이어 무어법은 배열을 1개만 사용해도 충분히 빠르다.보이어 무어법의 진행 과정예를 들어 보이어 무어법으로 텍스트 'ABCXDEZCABACABAC' 에서 패턴 'ABAC' 를 검색하는 과정을 살펴보자.먼저 위 그림처럼 텍스트와 패턴의 첫 문자를 위 아래로 나란히 놓고 패턴의 마지막 문자 'C'에 주목한다. 같은 위치에 있는 텍스트의 'X'는 패턴 안에 포함되어 있지..

KMP법이란?Knuth-Morris-Pratt법의 줄임말로 이 알고리즘을 고안한 크누스, 모리스, 프래트의 이름에서 따온 용어이다.브루트 포스법은 일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사를 수행하지만, KMP법은 검사 결과를 효율적으로 사용할 수 있다. KMP법 알아보기브루트 포스법은 일치하지 않는 문자를 만나면 이전 단계에서 검사했던 결과를 버리고 패턴의 첫 문자부터 다시 검색한다. 하지만 KMP법은 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘이다. 텍스트 'ZABCABXACCADEF'에서 패턴 'ABCABC'를 검색할 때 KMP법 알고리즘을 생각해보면 다음과 같다.1. 먼저 위의 그림처럼 텍스트와 패턴의 첫 문자부터 차례로 검사를 수행한다. 텍스트의 첫 문자 'Z'는 패..

문자열 검색이란?문자열 검색은 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것예를 들어 문자열 "STRING"에서 "IN"을 검색하면 성공하지만, 문자열 "QUEEN"에서 "IN"을 검색하면 실패함문자열 검색에서 검색되는 쪽의 문자열을 텍스트(text), 찾아내는 문자열을 패턴(pattern)이라고 함 브루트 포스법이란?문자열 검색 알고리즘 중 가장 기초적이고 단순한 알고리즘. 선형 검색을 단순하게 확장한 알고리즘이라서 단순법이라고 불린다.텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트 포스법으로 검색하는 순서는 다음과 같이 진행된다.1. 텍스트의 첫 문자 "A"에서 시작하는 문자 3개가 패턴 "ABC"와 일치하는지 검사한다."A..