algorithm to quickly find a pattern in a block

[SiliconWizard]

Note that Boyer-Moore can be more efficient than KMP but its worst case complexity is much worse. So if you are dealing with long patterns that are not very likely to repeat (contrary to letter patterns in text), I think I would personally favor KMP.

That said, the complexity of either may be significantly different when introducing wildcards. I haven't thought about it in details. I've implemented both wildcard match and KMP, but never both combined.

[DiTBho]

I haven't thought about it in details. I've implemented both wildcard match and KMP, but never both combined.

how did you implemented wildcards?

[SiliconWizard]

I'll give you the base version, which I think is pretty much the common way of implementing it efficiently. It handles patterns that contain '?' and '*', with the usual definitions for both wildcards. This version is for zero-terminated strings, but it's easy to modify it for arrays of bytes associated with a length. Returns true if the string matches the pattern, false otherwise.

Code: [Select]

bool PatternMatch(const char *szText, const char *szPattern)
{
if ((szText == NULL) || (szPattern == NULL))
return false;

if (*szPattern == '\0')
return (*szText == '\0');

const char *pText = NULL, *pPattern = NULL;

while (*szText != '\0')
{
if ((*szText == *szPattern) || (*szPattern == '?'))
{
szText++;
szPattern++;
}
else if (*szPattern == '*')
{
pText = szText;
pPattern = szPattern;
szPattern++;
}
else if (pPattern != NULL)
{
szText = pText + 1;
szPattern = pPattern + 1;
pText++;
}
else
{
return false;
}
}

while (*szPattern == '*')
szPattern++;

return (*szPattern == '\0');
}