보이어 무어 알고리즘

보이어 무어 알고리즘 보이어-무어 알고리즘은 문자열에서 문자열을 검색하는 알고리즘으로 검색하려는 문자열의 마지막 문자를 우선으로 비교하고, 다음으로 비교할 위치를 가리키는 index값을 효과적으로 조정해 비교 횟수를 줄인다. 1. 마지막 문자 우선 비교 찾으려는 문자열이 "abc"로 크기가 3이다. 따라서 첫 index값 또한 마지막 문자 비교를 위해 index=3-1 이 된다.(-1은 인덱스가 0부터 시작하므로) 아래의 "sesenn..."의 경우 매 비교마다 "abc"와 일치하는 문자가 없으므로 3씩 건너뛰며 검색을 수행한다. -> 7번의 비교로 끝 (마지막"dd"의 경우 인덱스 범위를 초과해 자동으로 검색 실패) 마지막 문자 우선비교 2. 효과적인 index값 조정 아래와 같이 "send"라는 문자열을 "sesann..."의 문자열 속에서 찾는다면, 첫 비교에서 "a"는 "send"에 포함되지 않으므로 "send"의 크기인 4만큼 index를 이동한다. 두 번째 비교에선 "s"...

원문링크 : 보이어 무어 알고리즘