c++函数实现*的正则匹配判断功能

今天在面试的时候面试官出了一道算法题,给出字符串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为,字符串为符合和不符合的情况

测试通过!!
有兴趣的朋友们可以自己下载程序试一试,同时欢迎提供更好的算法。

发表评论

邮箱地址不会被公开。 必填项已用*标注


*