Re: [go-nuts] Z algorithm in string package

[Ian Lance Taylor]

On Fri, Sep 17, 2021 at 8:38 AM vl4deee11 <vladboyc...@gmail.com> wrote:
>
> Hello everyone, I need help, I often write algorithms on strings, and often I need such a thing as a Z algo, is it possible to add it to a 'std/strings' package ?
> It can also be used in competitive programming, it is quite a useful thing.
>
> More about Z algo - https://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/

From a quick glance this looks like an efficient way of writing
strings.Contains or strings.Index. If somebody wants to write a
faster version of strings.Index, and can prove it using benchmarks, we
would be happy to include that in the standard library. strings.Index
is already pretty heavily optimized, but if we can make it faster we
will.

Ian

[Ian Lance Taylor]

On Fri, Sep 17, 2021 at 12:03 PM vl4deee11 <vladboyc...@gmail.com> wrote:
>
> Yes, this algorithm is mainly used to quickly find a substring in a string. O(n+m), where n=len(string), m=len(substring). I can run some tests to check, and post them here. But I would also like to add the z algorithm itself, this will be useful mainly for competitive programmers, and it will become even more popular in competition.

I don't understand what it means to add the z algorithm itself, but if
you don't mean strings.Index then that does not seem like something
that belongs in the Go standard library. See
https://golang.org/doc/faq#x_in_std . It would be perfectly fine in
third party library that people can import.

Ian


> пятница, 17 сентября 2021 г. в 19:54:51 UTC+1, Ian Lance Taylor:

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/40412bfb-ca84-4cf5-b094-710c10b00367n%40googlegroups.com.

[Brian Candler]

A tradeoff with this algorithm is the extra memory allocation required. Say you're using int32 to represent the substring length, then a string of length N and pattern length P needs a temporary memory allocation of size 4N+4P+4.  Hence I'm not sure this is a good fit for string.Index, especially when the pattern is only a handful of bytes as is often the case.

Another way you can already get linear search time is to use regular expressions.  Go's RE2 regexp library searches in linear time in the length of the string being searched, with no backtracking.

The time to *compile* the regular expression may not be linear in the length of the pattern (although for simple patterns I expect it would be near enough).  However, if you are repeatedly searching for the same pattern I think this is a good option.  Another benefit is that it can search for multiple patterns concurrently, at no extra cost.

On Saturday, 18 September 2021 at 07:57:05 UTC+1 vladboyc...@gmail.com wrote:

I think z algo can be third party lib. But i try to optimize strings.Index with z algo. Later i can show benchmarks. Thanks for your help!

пятница, 17 сентября 2021 г. в 22:07:00 UTC+3, Ian Lance Taylor: