《剑指offer》:[53]正则表达式匹配

      选择只有一种：在模式串上向后移动两个字符,忽略掉b和*，因为‘*‘可以匹配0个字符；如下图：

具体如下图所示：

#include <iostream>
using namespace std;
bool MatchCore(char *str,char *pattern)
{
	if(*str=='\0' && *pattern=='\0')
		return true;
	if(*str!='\0' && *pattern=='\0')
		return false;
	if(*(pattern+1)=='*')
	{
		if(*pattern==*str || (*pattern=='.' && *str!='\0'))//将‘*’号忽略，‘*’前的作为一个有效的值；
			return MatchCore(str+1,pattern+2) 
			|| MatchCore(str+1,pattern) //‘*’号前可以出现任意个，所以pattern可以保持不变
			|| MatchCore(str,pattern+2);//忽略‘*’及‘*’号以前的字符；
		else
			return MatchCore(str,pattern+2);//因为‘*’ 号前的字符与*str不等，所以只能忽略*pattern字符一个选择；
	}
	if(*str==*pattern || (*pattern=='.' && *str!='\0'))
		return MatchCore(str+1,pattern+1);//正常的字符串比较；
	return false;
}
bool match(char *str,char *pattern)
{
	if(str==NULL || pattern==NULL)
		return false;
	return MatchCore(str,pattern);
}
int main()
{
	char str[]="aaa";
	char *pattern[4]={"a.a","ab*ac*a","aa.a","ab*a"};
	for(int i=0;i<4;i++)
	{
		if(match(str,pattern[i]))
			cout<<"The same!"<<endl;
		else
			cout<<"Not the same!"<<endl;
	}
	system("pause");
	return 0;
}

运行结果：

《剑指offer》:[53]正则表达式匹配

原文：http://blog.csdn.net/gogokongyin/article/details/51776222