No.3014 多項式ハッシュに関する教育的な問題
タグ : / 解いたユーザー数 13
作問者 : anta
問題文
多項式ハッシュ(ローリングハッシュ, Karp-Rabin fingerprintとも呼ばれる)は、整数$P, B$をパラメーターとして取り、文字列$S$に対して \[ h_{P,B}(S) = (\sum_{i=1}^{|S|} B^{|S|-i} {\rm ord}(S_i)) \bmod P \] として定義される。ここで、$|S|$は$S$の長さを表す。${\rm ord}(c)$は文字$c$のアスキーコード('a'~'z'は97~122)を表す。$x \bmod P$として$x$を$P$で割った余りを表す。
$P$, $B$が与えられる。2つの文字列$S, T$であって、
- $S \neq T$
- $|S| = |T|$
- $1 \le |S|, |T| \le 10^5$
- $S, T$ はそれぞれ英小文字('a'~'z')のみからなる。
- $h_{P,B}(S) = h_{P,B}(T)$
入力
$P$ $B$
1行目と2行目に、多項式ハッシュ関数のパラメータである整数$P$と整数$B$が与えられる。
ただし、テストケースは1ケースだけであり、その内容は以下の通りであることが保証される。
1000000000000000003 123456789987654321
出力
$S$ $T$
問題文の条件を満たす$S, T$を2行に出力せよ。
サンプル
サンプル1
入力
1009 123
出力
bab wbe
$h_{P,B}(S) = h_{P,B}(T) = 342$となる。
サンプル2
入力
1000000007 123456789
出力
hkmpqvm axlszsi
$h_{P,B}(S) = h_{P,B}(T) = 409775251$となる。
ヒント
テストケースの$P,B$に特に深い意味はありません。
$0 \le B < P \le 10^{18}$であるとしても想定解法が任意の入力に対して制限時間内に必ず正しい答えを出力できることは保証されません。
ただし、単純な埋め込みではなく、テストケースに対しては制限時間内に答えを生成していることは確かです。
よって、埋め込み以外の方法で解いてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。