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

[sylvinus]

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]

@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]

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

[odeke-em]

Sorry about that! I didn't see #21463 (comment) 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]

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