Re: KMP Algorithm supporting * notation
- From: Tor Myklebust <tmyklebu@xxxxxxxxxxxxxxxxxxx>
- Date: Sun, 7 Oct 2007 06:06:20 +0000 (UTC)
Altu <altu59@xxxxxxxxx> wrote:
Hi,
Is it possible to extend the KMP algorithm to support * in patterns?
Like
ab*cd
and * can be any character but cannot be nothing.
The problem is that when I am looking at the character with index i in
the text, if it is not a match, I don't want to look at the previous
characters of the text (just like KMP).
Is this possible?
Yes. Split your string at every *; this gives you a list of patterns.
In your example, they are "ab" and "cd". You use KMP to find the first
occurrence of the first pattern, KMP again to find the first occurrence
of the second pattern after the first pattern, and so forth. If KMP
ever fails, your pattern does not occur; otherwise, it does occur.
.
- References:
- KMP Algorithm supporting * notation
- From: Altu
- KMP Algorithm supporting * notation
- Prev by Date: A question about regexes
- Next by Date: Re: A question about regexes
- Previous by thread: Re: KMP Algorithm supporting * notation
- Next by thread: A question about regexes
- Index(es):
Relevant Pages
|