说明

该代码解决的问题是判断两个给定的域名模式是否匹配。域名模式可以包含通配符（*、?、!），这些通配符分别匹配不同数量的域名部分。如果存在至少一个域名可以同时匹配这两个模式，则认为这两个模式匹配。

算法标签

• 字符串处理
• 动态规划
• 模式匹配

解题思路

1. 输入处理：读取测试用例的数量 t，然后逐个处理每个测试用例。每个测试用例包含两行，每行一个域名模式。
2. 模式转换：将每个域名模式转换为一个整数序列 s1 和 s2，其中：
   • 普通域名部分映射为唯一的正整数。
   • 通配符 * 转换为 -1 和 -2（匹配一个或多个部分）。
   • 通配符 ? 转换为 -1、-3、-3（匹配1到3个部分）。
   • 通配符 ! 转换为 -1、-1、-1、-2（匹配至少3个部分）。
3. 动态规划匹配：使用动态规划表 dp[i][j] 表示 s1 的前 i 个部分和 s2 的前 j 个部分是否可以匹配。填充动态规划表时，根据当前部分的类型（普通部分或通配符）进行匹配判断。
4. 结果输出：根据动态规划表的结果，输出 YES 或 NO。

分析

• 模式转换：将域名模式转换为整数序列，便于处理通配符和普通部分的匹配。通配符的转换规则确保了后续匹配逻辑的正确性。
• 动态规划：使用动态规划表记录匹配状态，逐步填充表格，确保所有可能的匹配情况都被考虑。这种方法能够高效地处理复杂的通配符匹配问题。
• 时间复杂度：动态规划表的大小为 O(l1 * l2)，其中 l1 和 l2 是两个模式的长度。在题目给定的约束下（模式长度最多255），该方法是可行的。

实现步骤

1. 读取输入：读取测试用例的数量 t，然后逐个处理每个测试用例。
2. 模式转换：将每个域名模式转换为整数序列 s1 和 s2，并记录其长度 l1 和 l2。
3. 初始化动态规划表：初始化 dp[0][0] = 1，表示空模式匹配空模式。
4. 填充动态规划表：遍历 s1 和 s2 的每个部分，根据当前部分的类型更新动态规划表。
5. 输出结果：根据 dp[l1][l2] 的值输出 YES 或 NO。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
#define N 1200
int s1[N],s2[N],l1,l2;
bool dp[N][N];
int t;
map<string,int>mp;
void trans(string s,int *t,int &len)
{
	len=0;
	for(int i=0;i<s.length();)
	{
		if(s[i]=='.')
		{
			i++;
			continue;
		}
		else
		if(s[i]=='*')
		t[++len]=-1,t[++len]=-2,i++;
		else
		if(s[i]=='?')
		t[++len]=-1,t[++len]=-3,t[++len]=-3,i++;
		else
		if(s[i]=='!')
		t[++len]=-1,t[++len]=-1,t[++len]=-1,t[++len]=-2,i++;
		else
		{
			int j;
			for(j=i+1;s[j]!='.'&&j<s.length();j++);
			string x=s.substr(i,j-i);
			if(!mp.count(x))
				mp[x]=mp.size()+1;
			t[++len]=mp[x];
			i=j+1;
		}
	}
}
void gao(int i,int j)
{
	if(s1[i]==-2||s2[j]==-2||s1[i]==-3)
	dp[i][j]=1;
	j++;
	if(j>l2)
	return;
	if(s1[i]>0)
	{
		for(int cnt=0;j<=l2;j++)
		{
			if(s2[j]>0&&s2[j]!=s1[i])
			break;
			if(s2[j]==-1||s2[j]>0)
			cnt++;
			if(cnt>1)
			break;
			dp[i][j]=1;
		}
	}
	else
	if(s1[i]==-2)
	for(;j<=l2;j++)
	dp[i][j]=1;
	else
	if(s1[i]==-3||s1[i]==-1)
	{
		for(int cnt=0;j<=l2;j++)
		{
			if(s2[j]==-1||s2[j]>0)
			cnt++;
			if(cnt>1)
			break;
			dp[i][j]=1;
		}
	}
}
void solve()
{
	dp[0][0]=1;
	for(int i=0;i<l1;i++)
	for(int j=0;j<=l2;j++)
	{
		if(dp[i][j]==0)
		continue;
		gao(i+1,j);
	}
	printf("%s\n",dp[l1][l2]==0?"NO":"YES");
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		mp.clear();
		string s;
		cin>>s;
		trans(s,s1,l1);
		cin>>s;
		trans(s,s2,l2);
		solve();
	}
	return 0;
}