P2635 带通配符的字符串匹配

    • 44通过
    • 181提交
  • 题目提供者 dropD
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 数论,数学 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,其中,“?”可以代替一个字符,而“*”可以代替零个或多个字符。

    现又定义一个通配符“@”,规定在一个字符串中,“@”代替的字符个数是固定的。

    题目描述

    用户在使用“@”时,当然希望输入的“@”越少越好。现在给出一个带有“?”“*”通配符的字符串和一个原字符串,要求首先判断通配符字符串与原字符串是否匹配,若匹配则求出将原通配符字符串中的“?”“*”字符替换为“@”且保证修改后的通配符字符串与原字符串匹配,最少需要多少个通配符“@”。

    输入输出格式

    输入格式:

    输入文件第一行为一个字符串,描述通配符字符串;

    第二行也为一个字符串,描述原字符串。

    输出格式:

    输出文件第一行为一个字符串,若通配符字符串与原字符串能够匹配则输出“matched”,并在接下来的一行输出一个整数,描述最少需要的通配符“@”的数量;若不匹配则输出“not matched”。

    输入输出样例

    输入样例#1: 复制
    1*456??
    111111145678
    输出样例#1: 复制
    matched
    4
    输入样例#2: 复制
    1*456
    1111111452
    输出样例#2: 复制
    not matched

    说明

    【样例说明1】

    两字符串显然可以匹配,通配符字符串1*456??可以替换为1@@@456@,最少需要4个“@”,其中每个“@”代替两个字符,可以证明,此为最优情况。

    通配符字符串1*456??也可以替换为1@@@@@@456@@,此时每个“@”代替一个字符,需要8个“@”,没有上面的情况优。

    【样例说明2】

    两字符串不可以匹配。

    【数据范围】

    对于100%的数据,字符串的长度均小于3000。

    保证原字符串中仅出现字母和数字,通配符字符串中仅出现字母、数字和通配符“?”“*”,且保证匹配方式唯一。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。