g*********s
发帖数: 1782 | 1 the regular expression only includes a-z, '*', and '.'
support:
1. "x*", aka 0 or more continuous 'x'
2. ".", aka wildcard matching any letter.
it seems back-trace is inevitable because of the following ambiguity:
match("b", "b*.") == true;
match("b", "b*") == true; | X****r
发帖数: 3557 | 2 Any formal regular expression can be mapped to finite state
machine, so you don't need to back-trace, i.e. you can scan
input string only once to match for any given regular expression.
【在 g*********s 的大作中提到】
: the regular expression only includes a-z, '*', and '.'
: support:
: 1. "x*", aka 0 or more continuous 'x'
: 2. ".", aka wildcard matching any letter.
: it seems back-trace is inevitable because of the following ambiguity:
: match("b", "b*.") == true;
: match("b", "b*") == true;
| g*********s
发帖数: 1782 | 3 yes, regex -> nfa -> dfa can completely solve the regex issue.
but what i expect here is some simplified solution for this simple regex.
or this is not simple as long as "*" is introduced, and a full fa based
solution is required?
【在 X****r 的大作中提到】
: Any formal regular expression can be mapped to finite state
: machine, so you don't need to back-trace, i.e. you can scan
: input string only once to match for any given regular expression.
| X****r
发帖数: 3557 | 4 For this simple regex you don't need to explicitly convert to DFA.
e.g. you can maintaining a list of possible 'leads' so far.
Of course, this won't be as efficient as pre-compute the
state table for the given regex, but if you want a simple one:
#define MAX_STARS 256
int match(const char *input, const char *regex) {
int p[2][MAX_STARS] = {0};
int c[2] = {1};
int w = 0, nw = 1, i, j;
char ch, nch;
for (; *input; input++) {
c[nw] = 0;
for (i = 0; i < c[w]; i++) {
j = p[w][i];
while (ch = regex[j]) {
nch = regex[j+1];
if (nch == '*') {
if (ch == '.' || ch == *input) {
p[nw][c[nw]++] = j;
}
j += 2;
} else {
if (ch == '.' || ch == *input) {
p[nw][c[nw]++] = j+1;
}
break;
}
}
}
w = nw;
nw = !nw;
}
for (i = 0; i < c[w]; i++) {
for (j = p[w][i]; regex[j] && regex[j+1] == '*'; j+= 2);
if (!regex[j]) {
return 1;
}
}
return 0;
}
(edit: damn BBS ruined the indent format, had to manually space...)
regex.
based
【在 g*********s 的大作中提到】
: yes, regex -> nfa -> dfa can completely solve the regex issue.
: but what i expect here is some simplified solution for this simple regex.
: or this is not simple as long as "*" is introduced, and a full fa based
: solution is required?
| g*********s
发帖数: 1782 | 5 found one in Beautiful Code by K&R's K.
so this is not a trivial question.
【在 X****r 的大作中提到】
: For this simple regex you don't need to explicitly convert to DFA.
: e.g. you can maintaining a list of possible 'leads' so far.
: Of course, this won't be as efficient as pre-compute the
: state table for the given regex, but if you want a simple one:
: #define MAX_STARS 256
: int match(const char *input, const char *regex) {
: int p[2][MAX_STARS] = {0};
: int c[2] = {1};
: int w = 0, nw = 1, i, j;
: char ch, nch;
| c*****t
发帖数: 1879 | 6 The question is, why write this kind of routine when scanf can
already do it?
【在 g*********s 的大作中提到】
: found one in Beautiful Code by K&R's K.
: so this is not a trivial question.
| g*********s
发帖数: 1782 | 7 why u learn classical algorithms when most of them already have been
implemented by stl and boost?
【在 c*****t 的大作中提到】
: The question is, why write this kind of routine when scanf can
: already do it?
| c*****t
发帖数: 1879 | 8 STL/Boost are for people to use. Trying to implement these yourselves
are quite silly.
Like goodbug once said, what was the point of learning algorithms when
one could just google + copy/paste? Having the right google skill
is far more important :)
I'd suggest you to do some real projects than working on some interview
questions or some specific functions.
【在 g*********s 的大作中提到】
: why u learn classical algorithms when most of them already have been
: implemented by stl and boost?
|
|
|
