dp wildcard.c

bool sphWildcardMatch ( const char * sString, const char * sPattern, int iDepth )
{
	if ( !sString || !sPattern || !*sString || !*sPattern )
		return false;

	int dTmp [SPH_MAX_WORD_LEN+1][SPH_MAX_WORD_LEN+1];
	const char * s = sString;
	const char * p = sPattern;

	dTmp[0][0] = 1;
	while ( *p )
	{
		int i = p - sPattern + 1;
		if ( *p=='*' )
			dTmp[i][0] = dTmp[i-1][0];
		else
			dTmp[i][0] = 0;
		p++;
	}

	p = sPattern;
	while ( *p )
	{
		int i = p - sPattern + 1;
		s = sString;
		while ( *s )
		{
			int j = s - sString + 1;
			if ( *p=='?' || *p==*s )
			{
				dTmp[i][j] = dTmp[i-1][j-1];
			} else if ( *p!='*' )
			{
				dTmp[i][j] = 0;
			} else
			{
				dTmp[i][j] = dTmp[i-1][j-1] || dTmp[i][j-1] || dTmp[i-1][j];
			}
			s++;
		}
		p++;
	}

	return dTmp[p-sPattern][s-sString];
}