今天在面试的时候面试官出了一道算法题，给出字符串a和字符串b，其中字符串a含有*，这个匹配所有的正则表达式符号，让写出一个函数判断字符串b是否符合规则，面试的时候有些紧张，思路又有些乱，写了一晚上终于成功了，这里提供一下我的算法，欢迎交流沟通。首先贴上完成的代码：
#include<iostream>
using namespace std;
/**********************************************************************
* 名 称：bool match(char *a, char *b, int startA, int startB)
* 功 能：匹配字符串b是否符合正则表达式规则
* 输入参数：字符串a（带*号匹配规则）, 字符串b（被匹配的字符）, a字符串开始的位置startA， b字符串开始的位置startB
* 返回参数：bool类型
-----------------------------------------------------------------------
* 说 明：无
***********************************************************************/
bool match(char *a, char *b, int startA, int startB)
{
//字符串a,b的长度
int lenA = strlen(a);
int lenB = strlen(b);
//posB,b字符串的startB位置标记
int posB = startB;
//a,b同时结束返回真
if(startA == lenA && startB == lenB)
{
return true;
}
//不是*开头 一定要匹配b
if(a[startA] != '*')
{
if(a[startA] != b[startB])
{
return false;
}
//递归
return match(a, b, ++startA, ++startB);
}else{
//是*开头 找到非*开始的地方
while(a[startA] == '*' && startA < lenA)
{
startA ++;
}
//以*结尾 同时遍历结束 返回真
if(startA == lenA && startB == lenB)
{
return true;
}
}
//记录a的位置
int posA = startA;
while(startB < lenB)
{
//遍历b找到 与startA 相同的字符
while(a[startA] != b[startB] && startB < lenB)
{
startB ++;
}
posB = startB;
//相同均++， a到头或者a遍历到*结束
while(a[startA] == b[startB] && startA < lenA && a[startA] != '*')
{
startA ++;
startB ++;
}
//a遍历到*并且没有结束的情况递归
while(a[startA] == '*' && startA < lenA)
{
return match(a, b, startA, startB);
}
//a,b同时到头的情况，返回true
if(startA == lenA && startB == lenB) {
return true;
}
//没有发现满足的字符串，b的startB + 1,在次做遍历
startA = posA;
startB = posB + 1;
}
return false;
}
void main()
{
char *a = "*a*b*c*";
char *b = "adbaeabeaeac";
bool c = match(a, b, 0, 0);
cout<<c<<endl;
}
算法解析：
函数是用C++写的，运用递归的思想。分为*开头和非*开头的情况。非*开头一路找到非*的位置开始匹配。
这里有个小坑，例如在字符串ababababcab中找abc的位置，这是比较常见的KMP算法，数据结构中有学，这里找到abc的位置后，两个字符串进行截取后再递归调用函数
测试用例:
分别进行了以下测试用例
字符串a为,字符串为符合和不符合的情况
测试通过！！
有兴趣的朋友们可以自己下载程序试一试，同时欢迎提供更好的算法。