16(0520) - kmp알고리즘 , 보이어 무어 알고리즘

1. kmp 알고리즘

kmp보다 보이어 무어가 더 좋다. (업그레이드된 버젼)

 

 

a는 접두사 밖에 없으므로 0

ab 는 접두사가 a 접미사가 b 이므로 0

aba 는 접두사가 a 접미사가 a 이므로 1

abac 는 접두사가 a, 접미사가 c  또는 접두사가 ab, 접미사가 ac 이므로 0

...

 

abab

abac 에서 접두사와 접미사가 ab로 같으므로 

 

b

c 가 다르기 때문에 abac 를 2칸 뒤로 옮긴다.

 

kmp 의 단점 :  문장이 길 경우에 접두사와 접미사가 같은지 확인하는 작업 또한 오래걸릴 수 있다.

---

2. 보이어 무어 알고리즘

보이어 무어는 끝에서부터 비교를 한다.

 

이번주 수요일 허프만코드 수업할 예정