CF730H.Delete Them
普及-
通过率:0%
时间限制:2.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Polycarp is a beginner programmer. He is studying how to use a command line.
Polycarp faced the following problem. There are n files in a directory and he needs to delete some of them. Polycarp wants to run a single delete command with filename pattern as an argument. All the files to be deleted should match the pattern and all other files shouldn't match the pattern.
Polycarp doesn't know about an asterisk '*', the only special character he knows is a question mark '?' which matches any single character. All other characters in the pattern match themselves only.
Formally, a pattern matches a filename if and only if they have equal lengths and all characters in the corresponding positions are equal except when the character in the pattern is '?', in which case the corresponding filename character does not matter.
For example, the filename pattern "a?ba?":
- matches filenames "aabaa", "abba.", "a.ba9" and "a.ba.";
- does not match filenames "aaba", "abaab", "aabaaa" and "aabaa.".
Help Polycarp find a pattern which matches files to be deleted and only them or report if there is no such pattern.
Polycarp 是一名初学编程者,正在学习如何使用命令行。
Polycarp 遇到了如下问题:某个目录下有 n 个文件,他需要删除其中一部分。Polycarp 希望仅执行一条带文件名模式(pattern)参数的删除命令。所有待删除的文件都必须匹配该模式,而其余所有文件都不得匹配该模式。
Polycarp 不了解星号 *,他唯一了解的特殊字符是问号 ?,它可匹配任意单个字符;模式中所有其他字符仅与自身匹配。
形式化地,一个模式匹配某文件名,当且仅当二者长度相等,且在每个对应位置上的字符均相等——除非模式中该位置为 ?,此时对应文件名中的字符可为任意字符。
例如,文件名模式 "a?ba?":
- 匹配文件名
"aabaa"、"abba."、"a.ba9"和"a.ba."; - 不匹配文件名
"aaba"、"abaab"、"aabaaa"和"aabaa."。
请帮助 Polycarp 找出一个恰好匹配所有待删除文件(且仅匹配这些文件)的模式;若不存在这样的模式,则报告无解。
输入格式
The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the total number of files and the number of files to be deleted.
The following n lines contain filenames, single filename per line. All filenames are non-empty strings containing only lowercase English letters, digits and dots ('.'). The length of each filename doesn't exceed 100. It is guaranteed that all filenames are distinct.
The last line of the input contains m distinct integer numbers in ascending order _a_1, _a_2, ..., a__m (1 ≤ a__i ≤ n) — indices of files to be deleted. All files are indexed from 1 to n in order of their appearance in the input.
输入的第一行包含两个整数 n 和 m(1 ≤ m ≤ n ≤ 100)—— 分别表示文件总数和待删除的文件数。
接下来的 n 行每行包含一个文件名。所有文件名均为非空字符串,仅由小写英文字母、数字和点号(.)组成。每个文件名的长度不超过 100。保证所有文件名互不相同。
输入的最后一行包含 m 个升序排列的互异整数 a1, a2, ..., am(1 ≤ ai ≤ n)—— 表示待删除文件的索引。所有文件按其在输入中出现的顺序从 1 到 n 编号。
输出格式
If the required pattern exists, print "Yes" in the first line of the output. The second line should contain the required pattern. If there are multiple solutions, print any of them.
If the required pattern doesn't exist, print the only line containing "No".
如果存在所需的模式,则在输出的第一行打印“Yes”。第二行应包含所需的模式。若存在多个解,输出任意一个即可。
如果不存在所需的模式,则仅在一行中输出“No”。
输入输出样例
输入#1
3 2 ab ac cd 1 2
输出#1
Yes a?
输入#2
5 3 test tezt test. .est tes. 1 4 5
输出#2
Yes ?es?
输入#3
4 4 a b c dd 1 2 3 4
输出#3
No
输入#4
6 3 .svn .git .... ... .. . 1 2 3
输出#4
Yes .???
输入解题思路,AI测评打分。不知道怎么写?