Replacing tango.text.Ascii.isearch

[Siarhei Siamashka]

On Wednesday, 5 October 2022 at 21:50:32 UTC, torhu wrote:
> I did some basic testing, and regex was two orders of magnitude 
> faster. So now I know, I guess.

Substring search functionality is currently in a very bad shape 
in Phobos. I discovered this myself a few weeks ago when I was 
trying to solve the 
https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/A2 puzzle using D language. A part of the solution requires a fast substring search (actually a subarray search) and Phobos doesn't offer anything with even remotely acceptable performance.

Phobos does have a Boyer-Moore implementation. This algorithm is 
historically famous in computer science as one of the first 
attempts to optimize substring search, but it also has 
pathologically bad performance on certain input data and probably 
shouldn't be recommended for any practical use nowadays. The 
users of old versions of Python discovered this too: 
https://codeforces.com/blog/entry/106849?#comment-952483

The standard 'find' function from the following simple example 
also becomes awfully slow when arrays 'a' and 'b' are large 
and/or are adversarially constructed:

```D
import std;
void main() {
   auto a = [1, 2, 3, 4];
   auto b = [2, 3];
   writefln("Is %s a subarray of %s? The answer is %s.",
            b, a, a.find(b).empty ? "no" : "yes");
}
```

I think that the best fit for your use case is the 
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm and there's an old issue in bugzilla about this: https://issues.dlang.org/show_bug.cgi?id=16066

BTW, if anyone is curious, one of the possible solutions for the 
hacker-cup/2022/round-1/problems/A2 puzzle in D language can be 
found here: 
https://codeforces.com/blog/entry/106768?#comment-952808