带通配符的字符串匹配

题目背景

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

题目描述

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

输入输出格式

输入格式


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

输出格式


输出文件第一行为一个字符串,若通配符字符串与原字符串能够匹配则输出“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。 保证原字符串中仅出现字母和数字,通配符字符串中仅出现字母、数字和通配符“?”“\*”,且保证匹配方式唯一。