[알고리즘 ] 16. 문자열 검색

공부한 날짜: 2021. 11. 04

 

 

1. 고지식한 검색(naive search, brute force search)

:  하나하나 비교해서 본문에서의 입력값을 찾는 알고리즘 

 

 

2. 카프 -라빈 알고리즘

: 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시 값을 비교해서 문자열을 찾는 알고리즘 

최초의 해시 값(H0)과 해당 문자열의 값(S[i])만 가지고 해당 문자열에 대한  해시 값을 구하고, 패턴의 해시값과 비교해서 단어를 찾는다 

(1) 해시 값 같은거 확인 (2) 각 문자 일일이 확인((해시 값이 같은 다른 문자열이 있을 수 있으므로)

 

 

3. KMP 알고리즘

: 비교가 필요한 부분만 비교를 수행하는 알고리즘 

 

-접두부/접미부/경계

접두부: 문자열의 머리 부분, 접미부: 문자열의 꼬리 부분, 경계: 문자열에서 일치하는 접두부와 접미부 쌍(하나의 문자열의 접두부와 접무부의 단어가 같은 경우)

 

-동작 원리

본문의 접미부와 패턴의 접두부가 동일하면 패턴이 그 단어의 접미부로 이동해서 비교해 나간다(?)

 

-경계의 정보를 갖는 테이블 만들기(경계를 효율적으로 찾기 위해서)

 

**원리 설명 부분 아직 이해 못함