kmp

보이어-무어 알고리즘(Boyer-Moore Algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다. 보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다. 오른쪽 끝과 일치하지 않는 경우 오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다. 만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다. 만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다. 오른쪽 끝과 일치하는 경우 오른쪽 끝 문..