3 ms·
>How do you extend Boyer-Moore to arbitrary regexps? As mentioned in the follow-up messages, some regexps can be translated to one or at least few fixed string
by wongarsu 12y ago
>How do you extend Boyer-Moore to arbitrary regexps?
As mentioned in the follow-up messages, some regexps can be translated to one or at least few fixed string searches (/^[Gg]rep/ is really a search for "\nGrep" or "\ngrep"). If you can't do that, your regexp may contain longish fixed strings that allow you to discard most lines via Boyer-Moore before you have to run the regexp engine.
For the more general case, http://swtch.com/~rsc/regexp/ http://swtch.com/~rsc/regexp/ provides great links.