ローリングハッシュとは
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
ハッシュ関数は文字列検索を高速におこなうアルゴリズムに応用することができます。そのアルゴリズムがローリングハッシュと呼ばれるものです。本問では、文字列検索をする前に、このローリングハッシュに用いられるハッシュ関数の特徴について考えてみましょう。
長さが L の文字列 S が与えられます。以下のハッシュ関数 H を用いて、この文字列の先頭の文字 ( 1 文字目) から i 文字目 (1 ≦ i ≦ L) までの文字列 s_i のハッシュ値をすべて計算してください。
文字列 s の長さを m として、
H(s) = (s の 1 文字目の文字コード * Bm-1 + s の 2 文字目の文字コード * Bm-2 + ... + s の m 文字目の文字コード * B0) % mod
ただし、B = 108+7, mod = 109+7 とし、文字コードは ASCII に従って変換してください。
- 入力される値
-
L
S- 1 行目に文字列の長さを表す整数 L が与えられます。
- 2 行目に長さが L の文字列 S が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
L 行出力してください。i (1 ≦ i ≦ L) 行目には、文字列 S の 1 文字目から i 文字目 までの文字列 s のハッシュ値 H(s_i) を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。H(s_1)
H(s_2)
...
H(s_L)
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 1 ≦ L ≦ 90000
- S は半角英数字で構成される長さ L の文字列
- 入力例1
-
5
paiza
- 出力例1
-
112
200000804
660005166
758032644
175605722
- 入力例2
-
10
1234567890
- 出力例2
-
49
900000365
170002312
271014612
907392103
16570263
404392714
947674143
270347118
503186883
