search

golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
124.13k stars 17.68k forks source link

regexp: Scan the input string backward for patterns ending in $ #21743

Open sylvinus opened 7 years ago

sylvinus commented 7 years ago

As suggested by @rsc:

It seems clear that we should handle patterns ending in $, like \.(jpe?g|gif)$, by scanning the string backward, which cuts the processing from O(n) to O(1) for an input of size n. That's easy to add to the existing matchers and doesn't need to be limited to fixed-size patterns.

I'm working on a CL to implement it for strings and byte slices.

odeke-em commented 7 years ago

@sylvinus thank you for creating the issue and for working on the CL. For posterity, I kindly wanted to ask if you could quote/provide the reference e.g with a link or so. This way, everyone interested in the issue can refer back to it and have context of the discussion.

sylvinus commented 7 years ago

Hi @odeke-em! Not sure what you mean because I've already included a link to his comment in this issue?

odeke-em commented 7 years ago

Sorry about that! I didn't see https://github.com/golang/go/issues/21463#issuecomment-326151555 as the hyperlink to suggested. Thanks for giving me a double check, I'll def go sleep, it is 5:29AM and am not clearly observing things :)

gopherbot commented 5 years ago

Change https://golang.org/cl/171417 mentions this issue: regexp: Scan backwards for patterns ending in $