www.pudn.com > StringM.rar > StringMatch.cpp

/*---------------------------------------------// 
作者:  苗人头领 
Email: gjjj2002@sina.com 
oicq:  7656312 
 
使用方法: 直接拷贝代码 
//---------------------------------------------*/ 
 
#include  
#include  
/*---------------------------------------------// 
作者:  苗人头领 
Email: gjjj2002@sina.com 
oicq:  7656312 
 
使用方法: 直接拷贝代码 
//---------------------------------------------*/ 
 
 
//功  能：在lpszSour中查找字符串lpszFind，lpszFind中可以包含通配字符‘?’ 
//参  数：nStart为在lpszSour中的起始查找位置 
//返回值：成功返回匹配位置，否则返回-1 
//注  意：Called by “bool MatchingString()” 
int FindingString(const char* lpszSour, const char* lpszFind, int nStart /* = 0 */) 
{ 
//	ASSERT(lpszSour && lpszFind && nStart >= 0); 
	if(lpszSour == NULL || lpszFind == NULL || nStart < 0) 
		return -1; 
 
	int m = strlen(lpszSour); 
	int n = strlen(lpszFind); 
 
	if( nStart+n > m ) 
		return -1; 
 
	if(n == 0) 
		return nStart; 
 
//KMP算法 
	int* next = new int[n]; 
	//得到查找字符串的next数组 
	{	n--; 
 
		int j, k; 
		j = 0; 
		k = -1; 
		next[0] = -1; 
 
		while(j < n) 
		{	if(k == -1 || lpszFind[k] == '?' || lpszFind[j] == lpszFind[k]) 
			{	j++; 
				k++; 
				next[j] = k; 
			} 
			else 
				k = next[k]; 
		} 
 
		n++; 
	} 
 
	int i = nStart, j = 0; 
	while(i < m && j < n) 
	{ 
		if(j == -1 || lpszFind[j] == '?' || lpszSour[i] == lpszFind[j]) 
		{	i++; 
			j++; 
		} 
		else 
			j = next[j]; 
	} 
 
	delete []next; 
 
	if(j >= n) 
		return i-n; 
	else 
		return -1; 
} 
 
//功	  能：带通配符的字符串匹配 
//参	  数：lpszSour是一个普通字符串； 
//			  lpszMatch是一可以包含通配符的字符串； 
//			  bMatchCase为0，不区分大小写，否则区分大小写。 
//返  回  值：匹配，返回1；否则返回0。 
//通配符意义： 
//		‘*’	代表任意字符串，包括空字符串； 
//		‘?’	代表任意一个字符，不能为空； 
//时	  间：	2001.11.02	13:00 
bool MatchingString(const char* lpszSour, const char* lpszMatch, bool bMatchCase /*  = true */) 
{ 
//	ASSERT(AfxIsValidString(lpszSour) && AfxIsValidString(lpszMatch)); 
	if(lpszSour == NULL || lpszMatch == NULL) 
		return false; 
 
	if(lpszMatch[0] == 0)//Is a empty string 
	{ 
		if(lpszSour[0] == 0) 
			return true; 
		else 
			return false; 
	} 
 
	int i = 0, j = 0; 
 
	//生成比较用临时源字符串'szSource' 
	char* szSource = 
		new char[ (j = strlen(lpszSour)+1) ]; 
 
	if( bMatchCase ) 
	{	//memcpy(szSource, lpszSour, j); 
		while( *(szSource+i) = *(lpszSour+i++) ); 
	} 
	else 
	{	//Lowercase 'lpszSour' to 'szSource' 
		i = 0; 
		while(lpszSour[i]) 
		{	if(lpszSour[i] >= 'A' && lpszSour[i] <= 'Z') 
				szSource[i] = lpszSour[i] - 'A' + 'a'; 
			else 
				szSource[i] = lpszSour[i]; 
 
			i++; 
		} 
		szSource[i] = 0; 
	} 
 
	//生成比较用临时匹配字符串'szMatcher' 
	char* szMatcher = new char[strlen(lpszMatch)+1]; 
 
	//把lpszMatch里面连续的“*”并成一个“*”后复制到szMatcher中 
	i = j = 0; 
	while(lpszMatch[i]) 
	{ 
		szMatcher[j++] = (!bMatchCase) ? 
								( (lpszMatch[i] >= 'A' && lpszMatch[i] <= 'Z') ?//Lowercase lpszMatch[i] to szMatcher[j] 
										lpszMatch[i] - 'A' + 'a' : 
										lpszMatch[i] 
								) : 
								lpszMatch[i];		 //Copy lpszMatch[i] to szMatcher[j] 
		//Merge '*' 
		if(lpszMatch[i] == '*') 
			while(lpszMatch[++i] == '*'); 
		else 
			i++; 
	} 
	szMatcher[j] = 0; 
 
	//开始进行匹配检查 
 
	int nMatchOffset, nSourOffset; 
 
	bool bIsMatched = true; 
	nMatchOffset = nSourOffset = 0; 
	while(szMatcher[nMatchOffset]) 
	{ 
		if(szMatcher[nMatchOffset] == '*') 
		{ 
			if(szMatcher[nMatchOffset+1] == 0) 
			{	//szMatcher[nMatchOffset]是最后一个字符 
 
				bIsMatched = true; 
				break; 
			} 
			else 
			{	//szMatcher[nMatchOffset+1]只能是'?'或普通字符 
 
				int nSubOffset = nMatchOffset+1; 
 
				while(szMatcher[nSubOffset]) 
				{	if(szMatcher[nSubOffset] == '*') 
						break; 
					nSubOffset++; 
				} 
 
				if( strlen(szSource+nSourOffset) < 
						size_t(nSubOffset-nMatchOffset-1) ) 
				{	//源字符串剩下的长度小于匹配串剩下要求长度 
					bIsMatched = false; //判定不匹配 
					break;			//退出 
				} 
 
				if(!szMatcher[nSubOffset])//nSubOffset is point to ender of 'szMatcher' 
				{	//检查剩下部分字符是否一一匹配 
 
					nSubOffset--; 
					int nTempSourOffset = strlen(szSource)-1; 
					//从后向前进行匹配 
					while(szMatcher[nSubOffset] != '*') 
					{ 
						if(szMatcher[nSubOffset] == '?') 
							; 
						else 
						{	if(szMatcher[nSubOffset] != szSource[nTempSourOffset]) 
							{	bIsMatched = false; 
								break; 
							} 
						} 
						nSubOffset--; 
						nTempSourOffset--; 
					} 
					break; 
				} 
				else//szMatcher[nSubOffset] == '*' 
				{	nSubOffset -= nMatchOffset; 
 
					char* szTempFinder = new char[nSubOffset]; 
					nSubOffset--; 
					memcpy(szTempFinder, szMatcher+nMatchOffset+1, nSubOffset); 
					szTempFinder[nSubOffset] = 0; 
 
					int nPos = ::FindingString(szSource+nSourOffset, szTempFinder, 0); 
					delete []szTempFinder; 
 
					if(nPos != -1)//在'szSource+nSourOffset'中找到szTempFinder 
					{	nMatchOffset += nSubOffset; 
						nSourOffset += (nPos+nSubOffset-1); 
					} 
					else 
					{	bIsMatched = false; 
						break; 
					} 
				} 
			} 
		}		//end of "if(szMatcher[nMatchOffset] == '*')" 
		else if(szMatcher[nMatchOffset] == '?') 
		{ 
			if(!szSource[nSourOffset]) 
			{	bIsMatched = false; 
				break; 
			} 
			if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1]) 
			{	//如果szMatcher[nMatchOffset]是最后一个字符， 
				//且szSource[nSourOffset]不是最后一个字符 
				bIsMatched = false; 
				break; 
			} 
			nMatchOffset++; 
			nSourOffset++; 
		} 
		else//szMatcher[nMatchOffset]为常规字符 
		{ 
			if(szSource[nSourOffset] != szMatcher[nMatchOffset]) 
			{	bIsMatched = false; 
				break; 
			} 
			if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1]) 
			{	bIsMatched = false; 
				break; 
			} 
			nMatchOffset++; 
			nSourOffset++; 
		} 
	} 
 
	delete []szSource; 
	delete []szMatcher; 
	return bIsMatched; 
} 
 
 
//-------------使用例子----------------// 
 
 
 
void main() 
{ 
	char* str = "String match"; 
	bool bMatch; 
	char* sMatch; 
 
	sMatch = "*ing??*c*"; 
	bMatch = MatchingString(str, sMatch,0);//单匹配 
	printf("\"%s\" %s match with \"%s\"\n\n", str, bMatch ? "is" : "is not", sMatch); 
 
	sMatch = "*ing??*c*??"; 
	bMatch = MatchingString(str, sMatch,0);//单匹配 
	printf("\"%s\" %s match with \"%s\"\n\n", str, bMatch ? "is" : "is not", sMatch); 
 
	 
}