這題看上去很冷門~
其實(shí)也是的，第一眼看上去想不到好的解法，但是將問題稍稍轉(zhuǎn)化一下就很好辦了。
思路：
兩個(gè)pattern匹配的過程，如果沒有通配符，那就是從左到右，逐個(gè)逐個(gè)的匹配。
由于存在通配符，a的一個(gè)節(jié)點(diǎn)有可能匹配b的數(shù)個(gè)節(jié)點(diǎn)，同樣，b的一個(gè)節(jié)點(diǎn)也有可能匹配a的數(shù)個(gè)節(jié)點(diǎn)。
這就需要搜索了。但是一開始發(fā)現(xiàn)搜索的時(shí)候通配符的處理真的很麻煩。感覺就是代碼稍微寫錯(cuò)一點(diǎn)就會(huì)WA。
于是想簡化一下問題。重新定義三種通配符：
ONE 匹配一個(gè)單詞
ZERO_ONE 匹配零個(gè)或一個(gè)單詞
ANY 可以匹配零個(gè)或多個(gè)單詞
這樣：
* = ONE, ANY
? = ONE, ZERO_ONE, ZERO_ONE
! = ONE, ONE, ONE, ANY
這樣做的好處是，避免了考慮通配符匹配的單詞數(shù)目。
規(guī)劃的時(shí)候處理 ONE, ZERO_ONE, ANY 是很簡單的。
f[a][b] = { 第一個(gè)pattern從a處開始匹配，第二個(gè)pattern從b處開始匹配，匹配成功則為1，否則為0 }
轉(zhuǎn)移的時(shí)候：
f[a][b] = {
pattern[1][a]為ANY的時(shí)候 = f[a + 1][b] || f[a][b + 1] || f[a + 1][b + 1]
pattern[1][a] 為ONE的時(shí)候 = {
pattern[2][b] 為 ONE 的時(shí)候 = f[a + 1][b + 1]
pattern[2][b] 為 ZERO_ONE 的時(shí)候 = 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;
}