Moore

Boyer-Moore (보이어무어) 알고리즘 / 문자열 탐색

개념 기존 고지식한 알고리즘과, KMP 알고리즘 혹은 지금까지 봐왔던 알고리즘들은 대부분 처음부터 비교해 나갈 것이지만 보이어-무어 알고리즘은 뒤에서부터 비교해나간다. 뒤에서부터 비교를 진행해 나가다 비교 값이 서로 다를 시 테이블을 참조해 나아간다. 아래는 보이어-무어 알고리즘으로 비교해 나아가는 이미지다. 뒤에서 비교하다 index 3번이 다르다는 것을 확인 후 테이블을 참조한다. 테이블을 참조 후 다음 비교할 위치로 건너뛴다. 그 다음 값을 보면 index 5, 6번이 다르지만 보이어-무어 알고리즘은 뒤에서부터 비교하므로 테이블 참조 시 index 6번에 대한 값을 참조하여 다음 비교 위치로 넘어긴다. 총 2번의 이동만으로 원하는 값을 찾아냈다. 만약 고지식한 알고리즘이었다면 2번 이동했을 때쯤 i..