ローリングハッシュを実装してみよう
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
ハッシュ関数は文字列検索を高速におこなうアルゴリズムに応用することができます。そのアルゴリズムがローリングハッシュです。本問では、このローリングハッシュを実装してみましょう。
長さが L の文字列 S が与えられます。その後、N 個の文字列 t_i (1 ≦ i ≦ N) が与えられます。文字列 S の中に t_i が部分文字列として含まれるかどうか以下のハッシュ関数 H を用いて判定し、含まれているならば Yes、含まれていないならば No とそれぞれについて出力してください。
文字列 s の長さを m として、
H(s) = (s の 1 文字目の文字コード * Bm-1 + s の 2 文字目の文字コード * Bm-2 + ... + s の m 文字目の文字コード * B0) % mod
ただし、B = 108+7, mod = 109+7 とし、文字コードは ASCII に従って変換してください。
また、同じ長さの 2 つの文字列 a と b のハッシュ値 H(a) と H(b) が一致したならば、a と b は同一の文字列であるとします。
- 入力される値
-
L N
S
t_1
t_2
...
t_n- 1 行目に、文字列 S の長さを表す整数 L と、調べたい文字列の数を表す整数 N が与えられます。
- 2 行目に、長さ L の文字列 S が与えられます。
- i + 2 行目に、調べたい文字列 t_i が与えられます。(1 ≦ i ≦ N)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
N 行出力してください。i (1 ≦ i ≦ N) 行目には、文字列 t_i が文字列 S の部分文字列として含まれているならば
Yes、そうでないならばNoと出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 1 ≦ L ≦ 20000
- 1 ≦ N ≦ 100
- S は半角英数字で構成される長さ L の文字列
- t_i は半角英数字で構成される長さ 1 以上 10 以下の文字列 (1 ≦ i ≦ N)
- 入力例1
-
5 4
paiza
b
ai
pizza
paiza
- 出力例1
-
No
Yes
No
Yes
- 入力例2
-
10 5
1234567890
59
9346
2
764
23
- 出力例2
-
No
No
Yes
No
Yes
