首页 > ACM题库 > HDU-杭电 > hdu 2585 Hotel-字符串处理-[解题报告]C++
2014
02-10

hdu 2585 Hotel-字符串处理-[解题报告]C++

Hotel

问题描述 :

Last year summer Max traveled to California for his vacation. He had a great time there: took many photos, visited famous universities, enjoyed beautiful beaches and tasted various delicious foods. It is such a good trip that Max plans to travel there one more time this year. Max is satisfied with the accommodation of the hotel he booked last year but he lost the card of that hotel and can not remember quite clearly what its name is. So Max searched
in the web for the information of hotels in California ans got piles of choice. Could you help Max pick out those that might be the right hotel?

输入:

Input may consist of several test data sets. For each data set, it can be format as below: For the first line, there is one string consisting of ‘*’,'?’and ‘a’-'z’characters.This string represents the hotel name that Max can remember.The ‘*’and ‘?’is wildcard characters. ‘*’ matches zero or more lowercase character (s),and ‘?’matches only one lowercase character.

In the next line there is one integer n(1<=n<=300)representing the number of hotel Max found ,and then n lines follow.Each line contains one string of lowercase character(s),the name of the hotel.
The length of every string doesn’t exceed 50.

输出:

Input may consist of several test data sets. For each data set, it can be format as below: For the first line, there is one string consisting of ‘*’,'?’and ‘a’-'z’characters.This string represents the hotel name that Max can remember.The ‘*’and ‘?’is wildcard characters. ‘*’ matches zero or more lowercase character (s),and ‘?’matches only one lowercase character.

In the next line there is one integer n(1<=n<=300)representing the number of hotel Max found ,and then n lines follow.Each line contains one string of lowercase character(s),the name of the hotel.
The length of every string doesn’t exceed 50.

样例输入:

herbert
2
amazon
herbert

?ert*
2
amazon
herbert

*
2
amazon
anything

herbert?
2
amazon
herber

样例输出:

1
0 
2
0

#include<iostream>
using namespace std;
int n,m;
char ans[55],src[55];
bool Find(char*pre,char*post)
{

   
if(*pre==’\0′&&*post==’\0′)returntrue;

   
if(*post==’*'&&*(post+1)==’\0′)returntrue;

   
if(*pre==*post)return Find(pre+1,post+1);
    else
if(*post==’?'&&*pre!=’\0′)return
Find(pre+1,post+1);
    else
if(*post==’*')
    {
       
while(*pre)
       
{
           
if(Find(pre+1,post))returntrue;
           
else return Find(pre+1,post+1);
       
}
    }
    else
returnfalse;
}
intmain()
{
   
while(scanf(“%s”,ans)!=EOF)
    {
       
scanf(“%d”,&n);
       
m=0;
       
while(n–)
       
{
           
scanf(“%s”,src);
           
if(Find(src,ans))
               
m++;
       
}
       
printf(“%d\n”,m);
    }
   
return0;
}



解题转自:http://blog.sina.com.cn/s/blog_b3dc8bf301016sgi.html


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.