Re: KMP Algorithm supporting * notation

On Sun, 07 Oct 2007 02:52:09 +0200, 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.

I would not use '*' for "one caracter, any one".
Because '*' in regexp usually means "the previous caracter can be here 0, 1 or several times" so using it for another meaning will probably confuse a lot of people...

I would advice to use instead either '?' (as in shell wildcards) or '.' (sed regexp).

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?

Without thinking a lot about it, I would say "yes" because KMP basically build the automaton corresponding to the pattern and pass the string through it. And the automaton for this pattern is very easy to build.
I may be wrong, however, due to some issues that might occur while determinising the automaton or similar bad stuff.


--
Hypocoristiquement,
Jym.
.

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)