테스트 데이터를 만들 때 즐겨 쓰는 데이터 들을 첨부합니다. 이 데이터들은 SCPC (삼성전자 대학생 프로그래밍 경진대회) 에도 활용 되었습니다.


내용이 간략하게만 쓰여져 있고, 정리 할 일이 있으면 길게 작성하도록 하겠습니다.


(판도라의 상자이므로 열지 마십시오)

AntiHash.pdf

AntiSort.pdf


  1. 안녕하세요, 좋은 글 감사합니다. 이번에 소멤 포스팅하면서 도움을 많이 받았습니다. 그런데 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))

  2. parity는 그냥 전체 bit를 xor한 값입니다.
    def parity(x):
    ret = 0
    while x:
    ret ^= (x&1)
    x >>= 1
    return ret
    # m = 2**32

+ Recent posts