61、腾讯现场招聘问题
liuchen1206
今天参加了腾讯的现场招聘会,碰到这个一个题目:
在一篇英文文章中查找指定的人名,人名使用二十六个英文字母(可以是大写或小写)、
空格以及两个通配符组成(*、?),通配符“*”表示零个或多个任意字母,通配符“?”表
示一个任意字母。
如:“J* Smi??” 可以匹配“John Smith” .
请用 C 语言实现如下函数:
void scan(const char* pszText, const char* pszName);
注:pszText 为整个文章字符,pszName 为要求匹配的英文名。
请完成些函数实现输出所有匹配的英文名,除了 printf 外,不能用第三方的库函数等。
/*
61、腾讯现场招聘问题
今天参加了腾讯的现场招聘会,碰到这个一个题目:
在一篇英文文章中查找指定的人名,人名使用二十六个英文字母(可以是大写或小写)、
空格以及两个通配符组成(*、?),通配符“*”表示零个或多个任意字母,通配符“?”表
示一个任意字母。
如:“J* Smi??” 可以匹配“John Smith” .
请用 C 语言实现如下函数:
void scan(const char* pszText, const char* pszName);
注:pszText 为整个文章字符,pszName 为要求匹配的英文名。
请完成些函数实现输出所有匹配的英文名,除了 printf 外,不能用第三方的库函数等。
这个算法,下面这种匹配也可以
txxxxxxtt
t*t
若要完全匹配 ,还需更改匹配成功的条件
*/
#include<iostream>
#include<stdio.h>
using namespace std;
const char *pEnd=NULL;
bool match(char *pszText,char *pszName)//一个字符一个字符的匹配
{
if(*pszName=='\0')//匹配完成
{
//if(*pszText!='\0') //整个匹配 就是前后都一样
// return false;
pEnd=pszText;//匹配字符个数0
return true;
}
if(*pszText=='\0')
{
if(*pszName=='*')
{
pEnd=pszText;//要匹配的是0,*可以匹配0个,所以匹配字符个数0
return true;
}
return false;
}
if(*pszName!='?'&&*pszName!='*')
{
if(*pszName==*pszText)
{
return match(pszText+1,pszName+1);
}
return false;
}
else if(*pszName=='*')//匹配0个或多个,继续*匹配下去
{
return (match(pszText+1,pszName)||match(pszText,pszName+1));
}
else
{
return match(pszText+1,pszName+1);
}
}
void scan( char *pszText, char *pszName)
{
while(*pszText!='\0') //不为空
{
if(match(pszText,pszName)) //匹配
{
while(pszText!=pEnd) //输出pszText到pEnd成功的
{
cout<<*pszText++;
}
cout<<endl;
}
return;
}
}
int main()
{
char pszText[100],pszName[100];
while(1)
{
fgets(pszText,100,stdin);
fgets(pszName,100,stdin);
cout<<"匹配结果:" ;
scan(pszText,pszName);
}
return 0;
}
/*
John Smith
J* Smi??
ttttttdd
*
txxxxxxtt
t*t
txxxxxxtt
t*t?
huxxx kk
*x ??
huxxx kk
*x ?
*/