Re: KMP Algorithm supporting * notation

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.
.

Relevant Pages

  • Re: RegEx: How to ignore the number of whitespaces?
    ... a "simpler" regular expression syntax is likely to bite you eventually, ... but that some of these character sequences may be "marked" as ... This is a regular expression "if" conditional statement, ... do not understand why the pattern "personal computer" will only match ...
    (microsoft.public.dotnet.framework)
  • Re: "String" manipulation for a Case clause
    ... ' Dim objRegExp As RegExp ... I would use Double or String. ... 'non-word character. ... 'construct a pattern like: ...
    (microsoft.public.excel.programming)
  • Re: empty displayed data except "space" and "newline"
    ... You don't need to remove spaces to put words into an array. ... .....Although you may want a different pattern than I use, ... upon your definition of "empty character". ... You said that that code is "For identifying whether it's an 'empty ...
    (perl.beginners)
  • Re: Musings on pacing
    ...  I know a novel should have a certain ... climactic moment differ from the composition of a climbing moment, ... three anyway) A character wants something and as he/or she tries to ... but the chapters follow an identical pattern and use the same ...
    (rec.arts.sf.composition)
  • Re: pattern matching question - please help
    ... Thanks for your detailed email and for your time. ... read on Perl did not mention anything about first and ... >> the pattern match ... a single character (basically, see references ...
    (perl.beginners)