15(0513) - 문자열 매칭

연습문제 답

1. 1번

2. 2번

3. 4번

4. 4번

 

4번 문제에서 h2(k) 는 h1(k) + 5 - (k mod 5 ) 의 결과가 나와야 한다.

---

오토마타 넘어감

 

라빈카프는 문자열을 수치화 시켜서 비교하는 방식이다.

앞에 5를 곱하는 이유는 c e b b 의 자릿수가 달라졌기 때문이다. +2 는 c를 뜻한다.

두 번째 a2 부터는 a1 즉 전의 계산된 수를 가지고 계산하기 때문에 속도가 빨라진다.