Fuzzy Matching

Googleが設立された初期のエンジニアだと想像してみてください。ユーザーが入力した文字列がデータベースに存在するかどうかを確認する検索機能を実装しようとしています。

まだ検索アルゴリズムを作り始めた段階なので、テスト用のデータセットとして、文字列が3種類の小文字 a, b, c のみからなる簡単な例を使っているとしましょう。

google-logo.jpg

データベースには n 個の文字列が格納されており、k 個のクエリが与えられます。検索を高速かつミスに強いものにするため、1文字だけの誤字(追加や削除はなし)を許容することにしました。

各クエリ文字列について、データベースに存在するかどうかを、最大1文字のミススペルを許容して判定する必要があります。

入力

最初の1行目には、整数 n (1 ≤ n ≤ 100 000) が含まれます。

続く n 行には、データベースに含まれる文字列 が書かれています。データベース内の文字列の長さの合計は 100 000 を超えないことが保証されています。

さらに、新たに1行を読み込み、整数 k (1 ≤ k ≤ 100 000) が与えられます。これはクエリの個数を表します。

続く k 行には、クエリ文字列 が書かれています。クエリ文字列の長さの合計も 100 000 を超えないことが保証されています。

出力

最大1文字の誤字を許容した上で、各クエリ文字列がデータベース内に存在するなら Yes、存在しない場合は No と出力してください。

入力

出力

2 aaabccc aaaaaac 4 aaabccc aabaccc aaaaaab aaaaaaaab

Yes No Yes No

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue