windcliff
BAN USERSimple iterative matcher, worst case O(m x n)
int match(const char* text, const char* pattern) {
if (!pattern || !text) {
return false;
}
// Iterate over all sub-strings in the string of the form
// text[0..n], text[1..n], text[2..n], ... , text[n..n]
const char* textItr = text;
while (*textItr) {
const char *patternItr = pattern;
bool match = true;
// Match the pattern against the current string in question.
while (*textItr && *patternItr) {
// The current character in the pattern
const char current = *patternItr;
// The lookahead character (for the kleene operator)
const char lookahead = *(patternItr + 1);
if (lookahead == '*') {
// This is a greedy operator
while (textItr && (current=='.' || current==*textItr)) {
++textItr;
}
patternItr += 2; // Skip forward two steps past '*'
} else {
if (current == '.') {
textItr++;
patternItr++;
} else if (current == *textItr) {
textItr++;
patternItr++;
} else {
match = false;
break;
}
}
}
// Need the latter part of the conditional
// to make sure we've matched the whole pattern
if (match && !(*patternItr)) {
return true;
}
++textItr;
}
return false;
}
Assuming I have no regular expression library to use:
- windcliff October 20, 2012