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: inserting all possible letter combinations into a phrase
    ... If strncmp is only going to compare one character, ... which is a compile time constant. ... cover all the non-@ characters in pattern. ... have an appropriate newsgroups line in your header for your mail to be seen, ...
    (comp.lang.c.moderated)