Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたはプログラマーとしてとある会社に勤めています。
この会社であなたは、ユーザーから集めた文字列のある連続した部分に指定した文字列が含まれるかを判定する業務をしています。
例えば、文字列 rhd
は文字列 thisisrhdcontest
に含まれていますが、文字列 thanks
や文字列 ratheads
には含まれていません。
しかしながら、ユーザーからの問い合わせにより、不要な文字がノイズとしてユーザーから寄せられた文字列に入ってしまいユーザーの希望通りの判定が行われていないことが判明しました。
そこであなたは、以下の Q 個のクエリ 1 から Q を処理するプログラムを作成することになりました。
クエリ i : 「文字列 S_i と文字列 T_i が与えられる。いくつかの文字 x_1, x_2, ... , x_k を選び (1 文字も選ばなくても良い)、文字列 S_i から選んだ文字をすべて取り除くという操作を行って得られる文字列 S'_i として考えられるものの中に文字列 T_i が含まれうるか判定せよ」
例えば、S_1 = ratheads
, T_1 = rhd
のとき、S_1 から文字 a
, e
, t
を取り除いたときに得られる文字列 S'_1 = rhds
には文字列 T_1 = rhd
が含まれるため、文字列 T_1 は含まれうるといえます。
入力
入力は以下の形式で標準入力から与えられる。
Q S_1 T_1 S_2 T_2 : S_Q T_Q
- 1 行目には、クエリの個数 Q (1 ≦ Q ≦ 5,000) が与えられる。
- 2 行目から Q 行には、クエリに関する情報が与えられる。このうち i (1 ≦ i ≦ Q) 行目には半角小文字英字のみで構成される 2 つの文字列 S_i, T_i (1 ≦ |S_i| ≦ 50, 1 ≦ |T_i| ≦ 50) が空白区切りで与えられる。
出力
Q 行にわたって出力せよ。Q 行のうち i (1 ≦ i ≦ Q) 行目には、クエリ i に対する答えを出力せよ。もしもクエリ i において文字列 T_i が含まれうるなら YES
を、そうでないなら NO
を出力せよ。出力の末尾にも改行を入れること。
入力例1
4 ratheads rhd thisisrhdcontest rhd yes no abba aba
出力例1
YES YES NO NO
クエリは 4 つあります。
- クエリ 1 は、問題文中の例に示されています。S_1 から文字
a
,e
,t
を取り除いたときに得られる文字列 S'_1 =rhds
には文字列 T_1 が含まれるので、YES
と出力します。 - クエリ 2 では、文字列 S_2 から文字を取り除かなくても文字列 S_2 に文字列 T_2 が含まれるので
YES
を出力します。 - クエリ 3 では、文字列 S_3 からどのように文字を取り除いても文字列 S'_3 に文字列 T_3 が含まれないので
NO
を出力します。 - クエリ 4 では、文字列 S_4 からどのように文字を取り除いても文字列 S'_4 に文字列 T_4 が含まれないので
NO
を出力します。
なお、文字を指定してその文字を取り除くとき、指定した文字を一部取り除かずに残すことができないことに注意してください。
入力例2
5 abcdef bdf aabbccdd b abcabcabc aaba abcdcba dba ababababa aba
出力例2
YES YES NO YES YES