2009百度笔试题解答

ladysfinger

（转）

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
均未出现错误。
解决该问题时，时间较为紧张，很多代码都存在隐患，并且没有添加注释，见谅，仅供参考！
另外，本人方法比较笨，希望高手指教！