同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2033_正则表达式匹配问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 34| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504261563000-Problem List-采集的数据-后羿采集器.html

Pro.ID

2033

Title

正则表达式匹配问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2033

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

许多操作系统采用正则表达式实现文件匹配功能。一种简单的正则表达式由英文字母、数字及通配符"*"和"?"组成。"?"代表任意一个字符。"*"则可以代表任意多个字符。现要用正则表达式对部分文件进行操作。

试设计一个算法，找出一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。所找出的正则表达式的长度还应是最短的。

输入

输入由n（1 ≤ n ≤ 250）行组成。每行给出一个文件名。文件名由英文字母和数字组成。英文字符要区分大小写，文件名长度不超过8个字符。文件名后是一个空格符和一个字符"+"或"-"。"+"表示要对该行给出的文件进行操作，"-"表示不进行操作。

输出

Description

Input

Output

输出最多文件匹配数和最优正则表达式。第一行是计算出的最多文件匹配数，第二行是最优正则表达式。

Sample Input

EXCHANGE +
EXTRA +
HARDWARE +
MOUSE -
NETWORK -

Sample Output

3
*A*

Author

John

样例输入