Best way to search for a subslice?

[awaw...@gmail.com]

Hi fellow Gophers

I wonder why is the `Index` function from the "slices" package much less powerful than the one in the "bytes" package?

`bytes.Index` allows us to search for {1, 2, 3} within {1, 1, 2, 3}, whereas `slices.Index` only does the trivial thing of whether a single 2 is inside {1, 1, 2, 3}.

What is the best way of doing `bytes.Index` but on say integer slices `[]int`?

Is it reasonable to propose adding a function `slices.IndexAll` to the "slices" package?

[Jason E. Aten]

On Tuesday, December 9, 2025 at 7:54:09 PM UTC-3 awaw... wrote:

What is the best way of doing `bytes.Index` but on say integer slices `[]int`?

This depends heavily on the length of the needle (query) versus the length 

of the haystack (database); and if you'll be doing repeated searches that might 

make it worth doing pre-processing of either one. You can read the wikipedia page 

for the Rabin–Karp string matching algorithm to get a sense of the issues involved.

Things like the expected versus worst-cases big-O times might be important, depending on

your use case, and there are various classical algorithms available that improve

on brute force in various circumstances.

https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

If you want deeper discussion, then CLR[1] and/or Dan Gusfield's book "Algorithms on Strings, Trees, and

Sequences" might be good reading.

[1] https://en.wikipedia.org/wiki/Introduction_to_Algorithms

That said, brute force search is often just fine as it tends to have a high L1-cache hit rate.

[awaw...@gmail.com]

Thanks Jason for the pointer to Rabin-Karp, it seems that this algorithm is indeed what `bytes.Index` uses.

That said I wonder is it appropriate to propose that this algorithm be implemented with generics in the "slices" package?

The current `slices.Index(x S, sep E)` seems a bit too primitive, and having a generic `IndexAll(x, sep S)` would be very helpful.

[tapi...@gmail.com]

From consistency view, the name should really be slices.IndexElem.

Maybe indexing subslices other than bytes and string is not common in practice.

[awaw...@gmail.com]

I'd argue indexing general slices is a pretty common need.

For example, right now I need to index `[]int` and `[]image.Point`.

To this end, I have submitted proposal https://github.com/golang/go/issues/76787 .