나한나한나한나

문자탐색 알고리즘

• 패턴의 오른쪽부터 비교
  • 텍스트 문자를 모두 비교하지 않아도 탐색이 가능한 알고리즘
• 문자열 패턴(찾고자 하는 문자)과 문자열을 비교 시 문자열의 가장 뒷부분 위치를 비교, 다르면 일정 길이만큼 이동하여 비교를 계속하는 기법
• 착한접미부 이동(Good suffix Method)와 나쁜문자 이동(Bad Character Method) 활용
• 현재 대부분의 워드프로세스 '검색' 기능에서 사용되고 있음

 

함께 공부할 문자열 검색 알고리즘

• 카프-라빈(Karp-Rabin) 검색 알고리즘
• 크누스-모리스-프랫(Knuth-Morris-Pratt, KMP) 알고리즘

 

나쁜문자 이동 방식

• 나쁜 문자란?
  • 본문의 문자열과 패턴이 불일치하도록 만드는 문자
  • 흐름
    • 1 - 나쁜 문자 발견
    • 2 - 패턴의 나쁜문자와 본문 문자열의 나쁜 문자 위치를 일치하도록 패턴 이