BOJ 13318 위험한 해싱

2020. 1. 19. 13:48알고리즘 문풀/BOJ 연습

https://www.acmicpc.net/problem/13318

 

13318번: 위험한 해싱

string matching 알고리즘에는 여러 가지가 있다. KMP 알고리즘이나 Boyer­Moore 알고리즘이 그 예시이다. 하지만 지구이는 KMP를 이해할 수 없었고, Boyer­Moore는 시간복잡도가 너무 컸다. 결국 지구이는 틀릴 확률이 있지만, 간단한 방법인 해싱을 즐겨 사용하게 되었다. 해싱은 문자열을 숫자 하나로 바꾸는 해시 함수를 하나 정의한 후, 이 값이 같은지 다른지를 통해 문자열이 같은지 판별하는 방법이다. 지구이는 해시 함수를 다음

www.acmicpc.net

풀이

두 해시값을 뺀 다항식을 생각하면, 그 다항식은 아래와 같은 조건을 만족해야 한다.

  • \(\deg f < 300000\)
  • \(f(x) = a_{0} + a_{1}x^{1} + \cdots + a_{d}x^{d}\)에서, \(-26 < a_{d} < 26\)
  • \(f(23) = f(29) = \cdots = f(67) = 0\) \(\text{mod}\) \(10^{9} + 7\)

하지만 다항식 하나에 10개의 영점을 강제하기는 너무 어렵다.

그래서 생각하기를 \(f_{1}(23) = 0\)을 만족하는 계수가 작은 다항식 \(f_{1}(x)\)를 찾고, 똑같이 \(f_{2}(29) = 0\)을 만족하는 계수가 작은 다항식 \(f_{2}(x)\)를 찾고, ... 그렇게 \(f(x) = f_{1}(x)f_{2}(x) \cdots f_{10}(x)\)로 쓰면 되지 않을까? 계수가 작은 다항식끼리 곱해서 계수가 많이 커지지는 않을 것 같다.

 

그럼 이제 \(f_{i}(x)\)를 잘 찾는 문제가 된다. 다항식을 10개로 쪼갰으니 평균 차수가 \(30000\) 이하여야 한다. 그런데 허탈하게도 \(f_{i}(x)\)는 다음 형태로만 잡아줘도 충분하다.

$$ f_{i}(x) = 1 \pm x^{\alpha} \pm x^{\beta} $$

 

대충 생각해 보면, \(p = 10^{9} + 7\)의 원시근이 많으니까 대부분 \(x^{\alpha}\)와 \(x^{\beta}\)는 다를 거고, 각각 \(30000\)개 정도 더하고 빼면 하나쯤 0이 나올 만하다. 이론적 근거가 있는지는 모르겠다. 있다면 제보해 주시길.

 

어쨌든 저 다항식들을 싸그리 곱해도 계수가 \(\pm 5\)는 넘어가지 않는 것 같다. Output only이기 때문에 충분한 디버깅을 거쳐서 기분좋게 한 방에 맞을 수 있다.

1 2 3 4 5 6 7 ··· 23