带通配符的字符串匹配

题目背景

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

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

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

输出文件第一行为一个字符串，若通配符字符串与原字符串能够匹配则输出“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。

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

对于字符st[i]讨论：

'?' :f[i][j] = f[i-1][j-1]

‘*’:f[i][j] = f[i-1][j-1] || f[i][j-1] || f[i-1][j] 

'1'~'9':f[i][j]=f[i-1][j-1] & a[i-1]==b[j-1]

代码：

#include <cstdio>
#include <cstring>
using namespace std;
char s[22], t[22];
bool f[22][22];

int main()
{
    scanf("%s %s", s+1, t+1);
    int m = strlen(s+1), n = strlen(t+1);
    f[0][0] = true;
    for (int i = 1; s[i] == '*'; ++i)
        f[i][0] = true;
    for (int i = 1; s[i]; ++i)
        for (int j = 1; t[j]; ++j) {
            if (s[i] == '?')
                f[i][j] = f[i-1][j-1];
            else if (s[i] == '*')
                f[i][j] = f[i-1][j] || f[i-1][j-1] || f[i][j-1];
            else
                f[i][j] = f[i-1][j-1] && (s[i] == t[j]);
        }
    puts(f[m][n] ? "matched" : "not matched");
    return 0;
}