테스트 데이터를 만들 때 즐겨 쓰는 데이터 들을 첨부합니다. 이 데이터들은 SCPC (삼성전자 대학생 프로그래밍 경진대회) 에도 활용 되었습니다.
내용이 간략하게만 쓰여져 있고, 정리 할 일이 있으면 길게 작성하도록 하겠습니다.
(판도라의 상자이므로 열지 마십시오)
AntiHash.pdf'프로그래밍 > 알고리즘' 카테고리의 다른 글
| Merry Problem Solving 2일차 (0) | 2018.12.24 |
|---|---|
| Merry Problem Solving 1일차 (0) | 2018.12.21 |
| 테스트 데이터 만들기: Anti-Hash test / Anti-Javasort test (2) | 2018.10.11 |
| 선형 점화식의 빠른 계산 (0) | 2018.07.24 |
| HYEA Online Judge 개발 (0) | 2018.07.06 |
| Simple Cubic General Maximum Matching Algorithm (0) | 2018.03.22 |
-
BaaaaaaaaaaaaaaaaaaaaaaarkingDog 2019.12.15 15:16 신고
안녕하세요, 좋은 글 감사합니다. 이번에 소멤 포스팅하면서 도움을 많이 받았습니다. 그런데 m이 2^32일 경우 (1-x)(1-x^2)(1-x^4)(1-x^8)(1-x^16)(1-x^32)(1-x^64)(1-x^128)으로 두면 2^28의 배수라 아직 부족하고 (1-x^256)까지 곱해져야 2^36의 배수가 되면서 충돌이 발생되어 길이가 512이어야 할 것 같은데 혹시 제가 잘못 이해한 부분이 있을까요?
저는 아래와 같이 코드를 만들었습니다.
def Collision3_32():
s1 = ''
s2 = 'b'*512
p = 243423223425 # any odd
m = 2**32
val = 0
for i in range(512):
if parity(i):
s1 += 'a'
else:
s1 += 'c'
print(RabinKarp(s1,p,m) == RabinKarp(s2,p,m))
-
BaaaaaaaaaaaaaaaaaaaaaaarkingDog 2019.12.15 15:17 신고
parity는 그냥 전체 bit를 xor한 값입니다.
def parity(x):
ret = 0
while x:
ret ^= (x&1)
x >>= 1
return ret
# m = 2**32
