CF514C.Watto and Mechanism

普及+/提高

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: "Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position".

Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of n initial lines and m queries. He decided to entrust this job to you.

瓦托(Watto)是一家零配件商店的老板,最近接到了一个订单,要求制造一种能够以特定方式处理字符串的装置。该装置的内存初始时存有 nn 个字符串。随后,该装置应能处理如下类型的查询:“给定字符串 ss,判断装置内存中是否存在字符串 tt,使得 ttss 长度相同,且恰好在一个位置上与 ss 不同”。

瓦托已经完成了该装置的硬件设计,目前仅需为其编写程序,并用包含 nn 个初始字符串和 mm 个查询的数据对其进行测试。他决定将这项任务交由你来完成。

输入格式

The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of the initial strings and the number of queries, respectively.

Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn't exceed 6·105. Each line consists only of letters 'a', 'b', 'c'.

第一行包含两个非负整数 nnmm0n31050 \leq n \leq 3\cdot10^50m31050 \leq m \leq 3\cdot10^5),分别表示初始字符串的个数和查询的个数。

接下来是 nn 个非空字符串,这些字符串被上传至该机制的内存中。

再接下来是 mm 个非空字符串,这些字符串是向该机制发出的查询。

输入中所有行的总长度不超过 61056\cdot10^5。每行仅由字母 'a'、'b'、'c' 组成。

输出格式

For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).

对于每个查询,如果该机制的内存中包含所需字符串,则在一行中输出 “YES”(不带引号),否则输出 “NO”(不带引号)。

输入输出样例

  • 输入#1

    2 3
    aaaaa
    acacaca
    aabaa
    ccacacc
    caaac

    输出#1

    YES
    NO
    NO

输入解题思路,AI测评打分。不知道怎么写?

首页