알고리즘 9 문자열 탐색

1. 고지식한 탐색의 동작 방식
-문자 바이 문자로 등호 검증 

2. 카프 라빈 알고리즘 
- 해시함수 계산을 가볍게 단축시켜서 검증하는 방법

3. KMP 알고리즘 
- 접두부와 접미부가 같은 경우, (Border = 경계)
  접두부-접미부 일치한 탐색이 한 차례 끝나고 나면, 
  그 다음 탐색은 바로 접미부부터 시작하면 된다
- 정확히는 -> 일치하는 부분 문자열의 길이 - 경계의 길이만큼 이동 
- 경계 정보 사전 계산 방법 

4. 보이어-무어 알고리즘 
- 불일치 발생 -> 불일치 문자가 본문에 없을 때 -> 일치한 패턴만큼 이동 
- 나쁜 문자 이동 ; 불일치 발생 시, 패턴에서 본문 불일치 문자를 오른쪽에서 부터 찾음 
                           -> 본문과 패턴의 불일치 문자가 같은 위치에 오도록 시프트
                           -> 너무 오른쪽에서 불일치문자가 발견될 경우 -방향으로 이동할수도?  
- 착한 접미부 이동 ; 불일치 발생 시, 본문의 접미부와 그 시점부터 패턴의 접미부를 찾음 
                           -> 접미부와 패턴의 부분을 일치시켜서 이동 
                           착한 접미부의 접미부와 매칭되는 게 있는지 확인 
                           -> 일치하는 곳까지 이동 
- 전처리 과정
  - 나쁜 문자 이동 테이블 만들기 ; 패턴 크기 테이블 > 문자별 가장 마지막 등장 위치 기록 
  - 착한 접미부 이동 테이블 : 패턴 길이 + 1 테이블 > 

 

 

Algorithm/StringAlgorithm at StringAlgorithm/text · Sukmin-LanternK/Algorithm