hanil0623   5달 전

라빈 카프로 문제를 풀고 싶습니다. power를 2씩 곱하고 모듈러 연산을 사용하지 않으니 틀렸다고 나오고

해시 충돌이 나서 그런가 싶어 모듈러와 power 값을 막 바꿔봐도 틀렸다고 나옵니다.

어떻게 해결할 수 있을까요? 아니면 제 코드가 잘못 된것일까요?

djm03178   5달 전

길이가 100만인 문자열에 10억 7 범위에서 해시를 할 경우 충돌이 발생할 확률은 1에 한없이 가깝습니다. 훨씬 더 큰 범위에서 해야 합니다.

길이가 100만이 아니라 10만이어도 충돌 확률이 이미 99%가 넘습니다.

hanil0623   5달 전

모듈러 값을 더 크게 해도 계속 오답이 나옵니다.

그럼 어떤 로직으로 바꿔야 하는건가요?

djm03178   5달 전

더 크게가 어느 정도인지는 모르겠지만 long long 전체 범위 정도는 써야 안전할 겁니다. 아니면 모듈로 값을 2개를 쓰셔도 되고요.

djm03178   5달 전

그리고 제가 라빈 카프에 대해 조예가 깊지 않아서 모르는 걸 수도 있겠으나 power 값을 중도에 바꾸는 건 처음 봅니다. 보통은 작은 소수 하나로 고정하고 하지 않나요?

hanil0623   5달 전

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220927272165&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

여기와 같이 a진법(power) 변환을 위해 비슷한 로직으로 해 봤습니다.

한번 더 시도해 보겠습니다.!

댓글을 작성하려면 로그인해야 합니다.