ノイズ除去
题意翻译
输入$2n$个字符串,一行两个,分别为$A_i$和$B_i$(仅由小写字母组成)。判断$B_i$在$A_i$去掉一些字母(可以不去)后是否为其子串
注:此处去掉一个字母,就是使这个字母在字符串里不再出现。(比如说你要去掉a',你必须把Ai里所有的'a'去掉,不能留一个)
然后,面对每一行的询问,若判断成立输出``YES``,反之输出``NO``
数据范围:$n \le 5000 $, $| a_i| , |b_i| \le 50$。
建议评分:入门~普及-
题目描述
[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2015-open/tasks/code_thanks_festival_2015_e
あなたはプログラマーとしてとある会社に勤めています。
この会社であなたは、ユーザーから集めた文字列のある連続した部分に指定した文字列が含まれるかを判定する業務をしています。
例えば、文字列 `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
输入样例 #2
5
abcdef bdf
aabbccdd b
abcabcabc aaba
abcdcba dba
ababababa aba
输出样例 #2
YES
YES
NO
YES
YES
说明
### Sample Explanation 1
クエリは $ 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` を出力します。 なお、文字を指定してその文字を取り除くとき、指定した文字を一部取り除かずに残すことができないことに注意してください。