a에서 z까지의 알파벳들을 사용하여
string이 구성될때요 (최대 길이 1500)
사용된 알파벳들의 갯수가 같으면, 같은 string이라고 처리하기 위해서 해싱을 해주더라구요
ex) aabcc == acbca
어떻게 해싱을 하는지 궁금하여 솔루션코드를 보는데요..
long long prime=1234567891;
hash_char['a'] = prime;
for(i='b' ; i<='z' ; i++) hash_char[i] = hash_char[i-1] * prime;
이런식으로 각각의 알파벳에 어떤 상수들을 지정해주더라구요.
그런데, long long 으로도 1234567891^26은 오버플로우가 나는데.. 왜 이렇게 해주는걸까요?
오버플로우가 나던 안나던, 이렇게 해주면.. 두 string의 hash code로 위의 조건에 대해 판별할 수 있나요?
http://hongjun-7.blogspot.kr/2014/12/hashing.html ㅎㅎ 읽고 해결할 수 있었습니당.. 혹 저랑 같은 궁금증 가지신분 위해 글은 삭제하지 않을게요..!
댓글을 작성하려면 로그인해야 합니다.
wyldecat 8년 전
a에서 z까지의 알파벳들을 사용하여
string이 구성될때요 (최대 길이 1500)
사용된 알파벳들의 갯수가 같으면, 같은 string이라고 처리하기 위해서 해싱을 해주더라구요
ex) aabcc == acbca
어떻게 해싱을 하는지 궁금하여 솔루션코드를 보는데요..
long long prime=1234567891;
hash_char['a'] = prime;
for(i='b' ; i<='z' ; i++) hash_char[i] = hash_char[i-1] * prime;
이런식으로 각각의 알파벳에 어떤 상수들을 지정해주더라구요.
그런데, long long 으로도 1234567891^26은 오버플로우가 나는데.. 왜 이렇게 해주는걸까요?
오버플로우가 나던 안나던, 이렇게 해주면.. 두 string의 hash code로 위의 조건에 대해 판별할 수 있나요?