[NOI1997] 文件匹配

很多操作系统都采用正则表达式来实现文件匹配功能。一种简单的正则表达式由英文字母（区分大小写）、数字及通配符 `*` 和 `?` 组成，`?` 代表任意一个字符，`*` 则可以代表零个或任意多个字符。 例如： 1. `a*b` 可以匹配 `acb`（`*` 代表 `c`）、`aabb`（`*` 代表 `ab`）、`asdsfdfdb`（`*` 代表 `sdsfdfd`）、`ab`（`*` 不代表任何字符）。 2. `a*b` 不可以匹配 `ac`（缺少最右边的字母 `b`）、`bb`（缺少最左边的字母 `a`）、`abbc`（最右边的字母不是 `b`）。 3. `a?b` 可以匹配 `acb`（`?` 代表 `c`）。 4. `a?b` 不可以匹配 `ab`（缺少中间的一个字符）、`accb`（`?` 只能代表一个字符）。 现要对某目录下的部分文件进行操作。写一个程序,寻找一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。注意你所找到的最优正则表达式的长度应当是**最短**的。 如果有多个长度最短的最优正则表达式，则其中任意一个都是允许的。 ## Input 第一行一个整数 $n$，表示字符串数量。 接下来 $n$ 行，每行一个字符串和一个字符（`+` 或 `-`），表示文件名（由英文字母和数字组成：英文字符区分大小写）和是否操作（`+` 表示要对该行给出的文件进行操作，`-` 表示不进行操作）。 ## Output 第一行一个整数，表示你找到的最优正则表达式所能匹配的文件数目。 第二行一个字符串，表示你找到的最优正则表达式。 [samples] ## Background **本题为上古 NOI 原题，未证明有无靠谱的正解可以通过。** 在计算机的日常操作中，经常需要对当前回录下的所有文件中的一部分文件进行操作。例如，将当前目录下的所有文本文件复制至另一个目录下、将当前目录下所有以 `a` 打头的文件删除，等等。 ## Note 对于 $5\%$ 的数据：$n=5$。\ 对于 $25\%$ 的数据：$5\le n\le 23$。\ 对于 $55\%$ 的数据：$5\le n\le 54$。\ 对于 $75\%$ 的数据：$5\le n\le 160$。\ 对于 $100\%$ 的数据：$5\le n\le 250,\ |S_i|\le8$。 为了便于调试和验证 Special Judge 的正确性，公布错误反馈信息和对应的含义： 1. `The number of matching file name(s) is wrong!` 你输出的数量不是最多的。 2. `The expression is longer than jury's expression!` 你输出的表达式不是最短的。 3. `The expression matches an invalid file name!` 你输出的表达式匹配了不进行操作的文件。 4. `The answer is correct.` 你输出的表达式符合题目要求。 5. `The expression is shorter than jury's expression ???` 你输出的表达式符合题目要求，且比现有最优表达式短。 6. `The expression is better than jury's expression ???` 你输出的表达式符合题目要求，且匹配的文件数目比现有最优表达式多。 7. `The number of matching file name(s) is false!` 你输出的表达式匹配的数量比你输出的数量少。 如果你遇到了 5、6 的评测错误情况，请找搬题人或者管理员，我们将修正数据。 感谢 Special Judge 来源：[Sprague_Garundy](https://www.luogu.com.cn/user/764746)。 感谢 hack 数据提供：[oOoOoOOOooOO](https://www.luogu.com.cn/user/42324)，位于单独的Subtask，不计分。