首页 > 试题广场 > poj 1229 Wild Domains
[问答题]
Consider a search engine that knows a number of sites. A site is described by a well-formed domain name which consists of two or more domain parts separated by dots such as www.sharif.edu. A domain part is a string of upper-case and lower-case alphabetic characters. For the rest of this description, we use the term domain name for well-formed domain name.

To restrict a search to some specific sites, a user is allowed to use domain patterns in a search query. A domain pattern is similar to a domain name, except that it may contain arbitrary number of the following wildcards:

  • Asterisk character (*) that matches a sequence of one or more domain parts separated by dots,
  • Question mark character (?) that matches at least one and at most three domain parts separated by dots,
  • Exclamation mark character (!) that matches at least three domain parts separated by dots.

Note that if a wildcard character appears in a domain pattern, it should be separated from its surrounding domain parts (if any) by dots. For example www.?.edu, or *.edu are both valid domain patterns matching domain name www.sharif.edu.

Two domain patterns match if at least one domain name can be constructed matching both domain patterns. For example, the domain patterns www.?.edu and *.edu match, since both match the domain name www.xyz.edu. Note that the constructed domain name may be an arbitrary (yet not necessarily an existing) site. You are to write a program that given two domain patterns, determines whether the patterns match.
输入描述
The first line of the input file contains a single intege
输出描述
There should be one line per test case in the output file containing a single word YES or NO, depending on whether the two domain patterns in the test case match or not.
输入例子
2
www.?.edu
?.edu
*.edu
yahoo.com
输出例子
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;
}
发表于 2015-10-28 15:17:26 回复(0)