POJ_1229
这个题目看到之后会有种想dp的感觉，但状态转移很不好搞。而之所以不好搞，就在于 ?和 !的限制过于繁琐，实际上如果是匹配符的话，一配一和一配任意是最好处理的，如果一配有限个就不那么好处理了，因此，一个思路就是把一配有限个转化成一配一和一配任意。
于是，我们把*、 ?、 !重新定义一下：
*：含义不变，至少配一个，多则不限。
?：只能配一个。
！：可以配一个，也可以什么都不配。
这样我们就得到了一个新旧通配符的转换公式：*->*， ?-> ?!!，！-> ??*。
至此，一配有限个的关系都被我们转化成一配一和一配任意的关系了，剩下的工作就是分情况将转移方程写出来即可。
#include<stdio.h>
#include<string.h>
#define MAXL 300
#define MAXD 600
char a[MAXD][MAXL], b[MAXD][MAXL], str[MAXL];
int A, B, dp[MAXD][MAXD];
void init()
{
int i, j, k;
A = B = 1;
scanf("%s", str);
for(i = 0;; ++ i)
{
for(j = 0; str[i] && str[i] != '.'; ++ i, ++ j)
a[A][j] = str[i];
a[A][j] = '\0';
k = A ++;
if(a[k][0] == '?')
{
a[A][0] = '!', ++ A;
a[A][0] = '!', ++ A;
}
else if(a[k][0] == '!')
{
a[k][0] = '?';
a[A][0] = '?', ++ A;
a[A][0] = '*', ++ A;
}
if(!str[i])
break;
}
scanf("%s", str);
for(i = 0;; ++ i)
{
for(j = 0; str[i] && str[i] != '.'; ++ i, ++ j)
b[B][j] = str[i];
b[B][j] = '\0';
k = B ++;
if(b[k][0] == '?')
{
b[B][0] = '!', ++ B;
b[B][0] = '!', ++ B;
}
else if(b[k][0] == '!')
{
b[k][0] = '?';
b[B][0] = '?', ++ B;
b[B][0] = '*', ++ B;
}
if(!str[i])
break;
}
}
void solve()
{
int i, j, k;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(i = 1; i < A; i ++)
for(j = 1; j < B; j ++)
{
if(a[i][0] != '*' && a[i][0] != '!' && a[i][0] != '?' && b[j][0] != '*' && b[j][0] != '?' && b[j][0] != '!')
{
if(strcmp(a[i], b[j]) == 0)
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 0;
}
else
{
if(a[i][0] == '*')
dp[i][j] = dp[i][j] || dp[i][j - 1] || dp[i - 1][j - 1];
if(a[i][0] == '?')
dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
if(a[i][0] == '!')
dp[i][j] = dp[i][j] || dp[i - 1][j - 1] || dp[i - 1][j];
if(b[j][0] == '*')
dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - 1];
if(b[j][0] == '?')
dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
if(b[j][0] == '!')
dp[i][j] = dp[i][j] || dp[i - 1][j - 1] || dp[i][j - 1];
}
}
if(dp[A - 1][B - 1])
printf("YES\n");
else
printf("NO\n");
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
init();
solve();
}
return 0;
}