알고리즘 - 보이어무어

▶보이어무어(Boyer - Moore)

 

⦁ 문자열 매칭이 마지막에 틀릴 가능성이 높다는 특징을 이용한다.

⦁ 검색할 패턴의 길이가 길고 텍스트 길이가 길 때 효율적이다.

⦁ 전체 문자열과 패턴을 비교 시 문자열의 뒷부분부터 비교하고 다르면 일정 길이만큼 이동한다.

⦁ 불일치 문자 규칙과 좋은 접미사 규칙을 사용한다.

 

 

 

 

• 불일치 문자 규칙(Bad Character Rule): 패턴의 불일치 문자가 텍스트에 존재하는 경우, 패턴을 오른쪽으로 이동시켜서 불일치 문자가 패턴 내에서 가장 오른쪽에 위치하도록 한다.
• 좋은 접미사 규칙(Good Suffix Rule): 패턴의 일치 접미사가 이미 확인된 경우, 패턴을 이동하여 이미 일치한 접미사가 다른 위치에서 다시 일치하도록 한다.

 

 

 

 

---

예제1

 

 

 

 

 

예제2

 

 

예제3

 

 

예제4

 

 

예제5