아.. kks님 코드 보신 거군요.
num이 무엇인지는 잘 모르겠습니다. 다만, 라빈 카프 알고리즘의 경우
<ABC>D에서
A<BCD>로 이동을 할 때 A<BC>D로 이동한 후에, A<BCD>로 이동하는데요.
<ABC>D에서 A<BC>D로 이동하는 과정에서 원래 rabin_finger값에 A*자릿수를 빼는 작업을 수행합니다. 이 과정에서 음수가 나올 수 있어요.
그 부분을 걱정하시는 것으로 보입니다... 네. 저 수식이 정당한지 보이려면, 법 MOD에 대해 모듈로 합동이냐만 보이면 됩니다. 3번째 줄이..
그러면 여기서 궁금하신 것은..
num이 음수일 때, ((-num / MOD + 1) * MOD + num)과 num이 법 MOD에 대해서 합동인가? 일 건데요. 아.. 이거 증명해 보면 되죠.
num = MOD*Q + r이라고 합시다. 이 때 0<=r<MOD일 겁니다. 그러면 Q<0일 건데.
-num = -MOD*Q - r입니다. 이것은, -MOD*Q - MOD + (MOD-r)로 쓸 수 있으므로 -(Q+1)MOD + (MOD-r)입니다. Q<0이므로, (Q+1)<=0입니다. Q는 정수이기 때문입니다.
이제 이것을 천천히 풀어봅시다.
((-num / MOD + 1) * MOD + num) % MOD는
(((-(Q+1)*MOD + (MOD-r)) / MOD + 1)*MOD + num) % MOD이고요. C언어에서 양수 나눗셈을 하면 몫만 취해집니다. 그러면 밑줄 친 부분은 -(Q+1)이 되겠네요.
((-(Q+1)+1)*MOD + num)%MOD = (Q*MOD + num)%MOD이고
Q는 정수이기 때문에, Q*MOD+num을 MOD로 나눈 나머지는 num을 MOD로 나눈 나머지와 같습니다. 법 MOD에 대해 합동이므로. 정당합니다.
PS. 굵게 칠한 부분은 스스로 증명해 보세요.
밤을 샜더니 비몽 사몽한 상태에서 쓰네요.. 혹여나 잘못된 부분 있다면 다시 질문 주세요..
jangzzang 4년 전 1
안녕하세요
라빈카프 알고리즘에 따라서 해싱을 수행하고 문자열을 옮겨가면서 해싱값계산을 해나갔습니다
라빈 카프 해시값 계산을 하면서 오버플로우에 대해서 제가 정확한 작동 방향이 이해가 안되서 질문을 드리는데요,
인터넷에 찾아보니
아래 소스처럼 mod 연산을 해 놓았더라구요. 오버 플로우가 나면 MOD배수를 더하여서 다시 양수로 만든 후, MOD로 나머지연산
취한다는 의미같은데, 이렇게 계산을 해도 해시값 자체에 문제가 없는 건가요?
문제가 없다는 의미가 예를들면
ABC DD ABC 가있을때 ABC를 계산하고 BCD에서 오버플로우가 난 후 다시 ABC를 계산하게 되는 과정에서 ABC의 해시값이ㅣ
고유하게 유지 될 수 있는 지가 궁금합니다.
감사합니다 :)