e.g. 输入：abcdefghabef, a*f 输出：abcdef

#include <iostream>
#include <string>
using namespace std;
bool Match(const string &s1,const string &s2,string &result)
{
	int i=0;
	if(s2.empty())//已经到了s2的尾部。说明都匹配了(s2和s1的推断顺序不能改)
		return true;
	if(s1.empty())//s1已经到了尾部。而s2还没到尾部，说明没有全然匹配
	{
		result="";
		return false;
	}
	if(s1[i]==s2[i])//假设相等，则匹配了一个元素。接着依次匹配下一个元素
	{
		result.push_back(s1[i]);
		Match(s1.substr(i+1),s2.substr(i+1),result);
	}
	else if(s2[i]==‘*‘)//假设遇到*号。则跳过*号，匹配s2的其它元素
	{

		Match(s1,s2.substr(i+1),result);
	}
	else//假设s1和s2的第一个元素不相等，则匹配s1的下一个元素
	{
		result.push_back(s1[i]);
		Match(s1.substr(i+1),s2,result);
	}
}
int main()
{
	string s1="abcdefghabef";
	string s2="a*f";
	string result;
	Match(s1,s2,result);
	cout<<result<<endl;
	return 0;
}

http://www.tuicool.com/articles/YZFJBb

http://wenku.it168.com/d_001232271.shtml