这题看上去很冷门~
其实也是的，第一眼看上去想不到好的解法，但是将问题稍稍转化一下就很好办了。
思路：
两个pattern匹配的过程，如果没有通配符，那就是从左到右，逐个逐个的匹配。
由于存在通配符，a的一个节点有可能匹配b的数个节点，同样，b的一个节点也有可能匹配a的数个节点。
这就需要搜索了。但是一开始发现搜索的时候通配符的处理真的很麻烦。感觉就是代码稍微写错一点就会WA。
于是想简化一下问题。重新定义三种通配符：
ONE 匹配一个单词
ZERO_ONE 匹配零个或一个单词
ANY 可以匹配零个或多个单词
这样：
* = ONE, ANY
? = ONE, ZERO_ONE, ZERO_ONE
! = ONE, ONE, ONE, ANY
这样做的好处是，避免了考虑通配符匹配的单词数目。
规划的时候处理 ONE, ZERO_ONE, ANY 是很简单的。
f[a][b] = { 第一个pattern从a处开始匹配，第二个pattern从b处开始匹配，匹配成功则为1，否则为0 }
转移的时候：
f[a][b] = {
pattern[1][a]为ANY的时候 = f[a + 1][b] || f[a][b + 1] || f[a + 1][b + 1]
pattern[1][a] 为ONE的时候 = {
pattern[2][b] 为 ONE 的时候 = f[a + 1][b + 1]
pattern[2][b] 为 ZERO_ONE 的时候 = f[a][b + 1] || f[a + 1][b + 1]
....
}
.....
}
#include <stdio.h>
#include <string.h>
struct _in 
{
char *arr[256], line[256];
int cnt;
} in[2];
enum _node_type {
ZERO_ONE, ONE, ANY, STR, END
};
struct _node {
enum _node_type type;
char *str;
} stk[2][512];
int dp[512][512], tm;
void input(struct _in *t)
{
int i;
scanf("%s", t->line);
for (i = t->cnt = 0; ; i++) {
t->arr[t->cnt++] = &t->line[i];
while (t->line[i] && t->line[i] != '.')
i++;
if (!t->line[i])
break;
t->line[i] = 0;
}
}
void init(struct _in *t, struct _node *s)
{
int i;
for (i = 0; i < t->cnt; i++) {
switch (*t->arr[i]) {
case '*':
s->type = ONE; s++;
s->type = ANY; s++;
break;
case '?':
s->type = ONE; s++;
s->type = ZERO_ONE; s++;
s->type = ZERO_ONE; s++;
break;
case '!':
s->type = ONE; s++;
s->type = ONE; s++;
s->type = ONE; s++;
s->type = ANY; s++;
break;
default:
s->type = STR;
s->str = t->arr[i];
s++;
break;
}
}
s->type = END;
}
int visited(struct _node *a, struct _node *b)
{
struct _node *t;
if (a > b) {
t = a;
a = b;
b = t;
}
return dp[a - stk[0]][b - stk[1]] == tm;
}
void set_visited(struct _node *a, struct _node *b)
{
struct _node *t;
if (a > b) {
t = a;
a = b;
b = t;
}
dp[a - stk[0]][b - stk[1]] = tm;
}
int match(struct _node *a, struct _node *b)
{
int r = -1;
if (visited(a, b))
return 0;
if (a->type == ONE) {
if (b->type == ONE)
r = match(a + 1, b + 1);
if (b->type == ZERO_ONE)
r = match(a, b + 1) || match(a + 1, b + 1);
if (b->type == ANY)
r = match(a, b + 1) || match(a + 1, b + 1) || match(a + 1, b);
if (b->type == STR)
r = match(a + 1, b + 1);
if (b->type == END)
r = 0;
}
if (a->type == ZERO_ONE) {
if (b->type == ZERO_ONE)
r = match(a + 1, b) || match(a, b + 1) || match(a + 1, b + 1);
if (b->type == ANY)
r = match(a + 1, b) || match(a, b + 1) || match(a + 1, b + 1);
if (b->type == STR)
r = match(a + 1, b + 1);
if (b->type == END)
r = match(a + 1, b);
}
if (a->type == ANY) {
if (b->type == ANY)
r = match(a + 1, b) || match(a, b + 1) || match(a + 1, b + 1);
if (b->type == STR)
r = match(a + 1, b) || match(a, b + 1) || match(a + 1, b + 1);
if (b->type == END)
r = match(a + 1, b);
}
if (a->type == STR) {
if (b->type == STR)
r = !strcmp(a->str, b->str) ? match(a + 1, b + 1) : 0;
if (b->type == END)
r = 0;
}
if (a->type == END) {
if (b->type == END)
r = 1;
}
if (r == -1)
r = match(b, a);
if (!r)
set_visited(a, b);
return r;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
input(&in[0]);
input(&in[1]);
init(&in[0], stk[0]);
init(&in[1], stk[1]);
tm++;
printf("%s\n", match(stk[0], stk[1]) ? "YES" : "NO");
}
return 0;
}