#4278. 「2021.03四级」带通配符的字符串匹配 普及−

题目背景

通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。

通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。

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

题目描述

用户在使用“@”时，当然希望输入的“@”越少越好。

现在给出一个带有“?”“*”通配符的字符串和一个原字符串，要求首先判断通配符字符串与原字符串是否匹配，

若匹配则求出将原通配符字符串中的“?”“*”字符替换为“@”且保证修改后的通配符字符串与原字符串匹配，最少需要多少个通配符“@”。

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

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

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

样例输入 1

1*456??
111111145678

样例输出 1

matched
4

样例解释 1

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

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

样例输入 2

1*456
1111111452

样例输出 2

not matched

样例解释 2

两字符串不可以匹配

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

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