应届生求职网手机APP

应届生求职招聘论坛

QQ登录

只需一步,快速开始

查看: 10311|回复: 39

[笔试] 2009百度笔试题解答

[复制链接]

主题

好友

1122

积分

地区经理

发表于 2009-10-10 16:05 |显示全部楼层
(转)

1 编写一个简单的支持正则表达式的字符串匹配函数,简单的正则表达式如下:

字符                     含义
c                        匹配字符c
.                         匹配任意一个字符
*                        若一个字符后紧跟*,则匹配0个或多个此字符

函数原型如下,参数regexp是待匹配的正则字符串,text是原始字符串。如果text中包含该正则串,函数返回1,否则返回0。建议先写明解题思路,再编码。
int  match(const char* regexp, const char* text);
例如:regexp:        c*       text:ccccc   返回1
A*              Abcd     返回1
A*              bbcd     返回0

思路:处理较为简单的*和。的组合。假设不出现连续多个* , 也不会出现连续多个. 有可能出现的情况是:    . ; *;  .*;
1)如果,出现了一个。那么,主串下标i自加, 字串j自加。如果下一个字符是*, 则找到*后面的字符,主串下标自加直到regexp[i]==字串*后面的字符为止。这时候求的是主穿中与*后面字符第一次匹配的情形,有可能后面还有匹配的情况,则在外面使用while循环,里面从主串和字串中相等的字符串后面的字符开始递归调用match函数如果后面的匹配了,又前面的已经匹配了,则整个匹配。否则,while循环寻找下个匹配的字符。循环执行。
2)如果出现了一个*, 说明这个*是单独出现的,若出现在.后面则在上面的1)中肯定处理完了。此处出现说明是单独出现,寻找*后面的字符,在主串中寻找第一个匹配的字符,另外要注意,匹配的字符前面的字符应该是相等的(*的缘故)。同1)由于可能存在多个匹配,使用while(i < strlen(regexp)) 并且循环里面利用递归match判断后面的时候匹配。
3)如果出现的既不是*有不是.那么肯定是正常字符,可以使用最笨的方法匹配,相等则i++,j++,不相等可以利用最笨的方法,i=i-j+1;j=0;也可以利用KMP算法不回溯。本人利用笨的了,呵呵。懒的把KMP弄上面来了。
算法如下:
#include <stdio.h>

int match(const char *regexp, const char *text)
{
int len1 = strlen(regexp);
int len2 = strlen(text);

int i=0;
int j=0;
int flag;
char ch, next;
while (i < len1 && j < len2)
{
ch = text[j];
if( ch == '.')
{
i++;
j++;
if( j >= len2)
{
printf("match\n");
return 1;
}
next = text[j];

if( next == '*')
{
j++;
if(j >= len2)
{
printf("match\n");
return 1;
}
ch = text[j];

while( i < len1)
{
while( regexp[i] != ch && i < len1)
{
i++;
}
if( ++j < len2)
{            
if(++i < len1)
{
flag = match(&regexp[i], &text[j]);
if(flag == 1)
{
printf("match\n");
return 1;
}
}
else
{
printf("mismatch\n");
return 0;
}
}
else
{
printf("match");
return 1;
}
}
}
}
else if( ch == '*')
{
ch = text[j-1];
j++;
if(j >= len2)
{
printf("match");
return 1;
}

next = text[j];
while( i < len1)
{
while( i<len1 && regexp[i] != next)
{
if(regexp[i] != ch)
{
printf("mismatch");
return 0;
}

i++;
}

i++;
j++;
if( j >= len2)
{
printf("match");
return 1;
}
if( i>=len1 && (j +1 >= len2) && ( text[j] == '*'))//用以匹配AA   A*A*等regexp短而text长并且   
// text最后一个字符是*的情况
{
printf("match");
return 1;
}
if(i < len1)
{
flag = match(&regexp[i], &text[j]);
if(flag == 1)
{
printf("match");
return 1;
}
}
else
{
printf("mismatch");
return 0;
}
}
}
else
{
if( regexp[i] == text[j])
{
i++;
j++;
if( j >= len2)
{
printf("match");
return 1;
}

}
else
{
i = i-j+1;
j=0;
}
}
}
}



int main()
{
const char *str1 = "AEGFBCDF";
const char *str2 = "A.*BCD*F";

int flag = match(str1, str2);
if(flag== 1)
printf("%s matches %s\n", str1, str2);

return 0;
}

实验:A* ,  Abcd
A*,  bbcd
.A.*C    eABC  
A.*BCD*F    AEGFBCDF
均未出现错误。
解决该问题时,时间较为紧张,很多代码都存在隐患,并且没有添加注释,见谅,仅供参考!
另外,本人方法比较笨,希望高手指教!
回复

使用道具 举报

主题

好友

24

积分

求职中

发表于 2009-10-10 16:14 |显示全部楼层
顶一下再看!
回复

使用道具 举报

主题

好友

12

积分

求职中

发表于 2009-10-10 19:36 |显示全部楼层
ddddddddddd
回复

使用道具 举报

windabc      

主题

好友

914

积分

地区经理

发表于 2009-10-10 21:42 |显示全部楼层
大写字符C是匹配小写字符c么
回复

使用道具 举报

主题

好友

23

积分

求职中

发表于 2009-10-11 10:24 |显示全部楼层
刚接到百度的笔试通知。谢谢分享。希望有用。。。。。。。。。。。
回复

使用道具 举报

主题

好友

36

积分

职员

发表于 2009-10-11 13:31 |显示全部楼层
zan~~~~~~~~~~~~~~~`
回复

使用道具 举报

主题

好友

66

积分

职员

发表于 2009-10-11 14:28 |显示全部楼层
赞一下楼主,哈哈
回复

使用道具 举报

主题

好友

15

积分

求职中

发表于 2009-10-11 14:48 |显示全部楼层
顶!我也收到了通知
回复

使用道具 举报

主题

好友

45

积分

职员

发表于 2009-10-11 16:10 |显示全部楼层
代码之美的第一章有一个很好的正则表达式C语言的代码,能够满足楼主的要求,而且程序本身写得确实够经典。
回复

使用道具 举报

主题

好友

31

积分

职员

发表于 2009-10-11 18:33 |显示全部楼层
好帖,先顶了!
回复

使用道具 举报

主题

好友

217

积分

项目经理

发表于 2009-10-11 18:48 |显示全部楼层
谢谢@@@!!!
回复

使用道具 举报

主题

好友

142

积分

项目经理

发表于 2009-10-11 19:10 |显示全部楼层
好帖子。。。。。。
回复

使用道具 举报

主题

好友

26

积分

求职中

发表于 2009-10-11 19:28 |显示全部楼层
haohaoahoahoahaoh
回复

使用道具 举报

earlyup      

主题

好友

17

积分

求职中

发表于 2009-10-11 23:15 |显示全部楼层
虽然只有一题,还是非常不错!!
回复

使用道具 举报

mj0321      

主题

好友

25

积分

求职中

发表于 2009-10-12 08:14 |显示全部楼层
非常感谢楼主的分享!
回复

使用道具 举报

主题

好友

25

积分

求职中

发表于 2009-10-12 11:57 |显示全部楼层
楼主都笔试过了啊 迅猛啊
回复

使用道具 举报

主题

好友

64

积分

职员

发表于 2009-10-12 13:14 |显示全部楼层
感谢感谢感谢~
回复

使用道具 举报

主题

好友

887

积分

地区经理

发表于 2009-10-12 13:29 |显示全部楼层
这个~~~~~~不过不知道商业分析师是什么题木
回复

使用道具 举报

主题

好友

180

积分

项目经理

发表于 2009-10-12 21:14 |显示全部楼层
thx for sharing
回复

使用道具 举报

主题

好友

20

积分

求职中

发表于 2009-10-13 11:07 |显示全部楼层
dddddddddddddddd
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐上一条 /1 下一条


应届生求职网APP扫码下载

应届生APP|Archiver|应届生求职网YingJieSheng.COM ( 沪ICP备12015550号-13 )

GMT+8, 2019-11-14 13:10

Powered by Discuz!

© 2001-2012 Comsenz Inc.

           

快速回复 返回顶部 返回列表