给你两个域名，域名中包含一些通配符。
* ：匹配一个或任意多个部分
？：匹配一个或三个部分
！：匹配三个以上部分。
求这两个域名是否能够表示同一个域名？
域名的长度不超过255.
分析：设给出的域名为A，B，以f[i][j]表示域名A的前i个部分和域名B的前j个部分是否可能相同。类似于求最长公共子串的转移方式。
f[i][j]=f[i-1][j-1]||f[i][j-1] 如果A[i]是*号。
f[i][j]=f[i-1][j-1]||f[i-1][j-2]||f[i-1][j-3] //如果A[i]是？号，但这么写是有问题的。如果B[j]也是通配符，就错了。
于是我们势必将A[i]和B[j]一起考虑。这里就会有最多16种情况，当然其中有些情况可以合并。
但是仍然有问题。比如A[i]是？号，B[j]是?号。
如果方程这样写：f[i][j]=f[i-1][j-1]||f[i-1][j-2]||f[i-1][j-3]||f[i-2][j-1]||f[i-3][j-1] ，则如果B[j-1]是！号，则有问题。
如果方程这样写：f[i][j]=f[i-1][j-1]||f[i][j-1]||f[i-1][j]，则如果f[i][j-1]=1，但此时A[i]已经表示了三个部分了，没办法再表示B[j]了，又怎么办呢？
所以这种转移是很不好办的。
我们感觉到，如果通配符只能表示0个，1个或任意多个是比较好处理的。所以，我们将原有的通配符做一个转换。
*意义不变
？变成只能匹配一个部分
！变成只能匹配0个或1个部分。
则原来的？=？！！（新符号）
原来的！=？？*
这样的话，就好处理多了。
先考虑*号，再考虑！号，再考虑？或非通配符。具体转移看代码。
#include<iostream>
#include<cstdio>
#include<sstream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,cas;
#define MAXN 800
char s[MAXN][MAXN],t[MAXN][MAXN];
char ss[MAXN],tt[MAXN];
bool f[MAXN][MAXN];
int cnt1=,cnt2=,pos=;
int convert(char *ss,char s[][MAXN])
{
int cnt=,pos=;
int slen=strlen(ss);
for(int i=;i<slen;i++)
{
if(ss[i]!='.')
{
if(ss[i]=='!')
{s[cnt++][]='?';
s[cnt++][]='?';
s[cnt][]='*';
}
else if(ss[i]=='?')
{
s[cnt++][]='?';
s[cnt++][]='!';
s[cnt][]='!';
}
else s[cnt][pos++]=ss[i];
}
else
cnt++,pos=;
}
return cnt;
}
int main()
{
scanf("%d\n",&cas);
while(cas--)
{
memset(f,,sizeof f);
memset(s,,sizeof s);
memset(t,,sizeof t);
gets(ss);
//cerr<<ss<<endl;
gets(tt);
//cerr<<tt<<endl;
cnt1=convert(ss,s);
cnt2=convert(tt,t);
f[][]=;
for(int i=;i<=cnt1;i++)
for(int j=;j<=cnt2;j++)
{
if(s[i][]=='*')
f[i][j]=f[i][j]||f[i][j-]||f[i-][j-];
if(t[j][]=='*')
f[i][j]=f[i][j]||f[i-][j]||f[i-][j-]; else if(s[i][]=='!')
f[i][j]=f[i][j]||f[i-][j]||f[i-][j-];
else if(t[j][]=='!')
f[i][j]=f[i][j]||f[i][j-]||f[i-][j-];
else if(s[i][]=='?'||t[j][]=='?')
{
f[i][j]=f[i][j]||f[i-][j-];
}
else if(strcmp(s[i],t[j])==)
f[i][j]=f[i-][j-];
}
if(f[cnt1][cnt2]==)
printf("NO\n");
else printf("YES\n");
}
}