I make simple strings.Index using the z-algorithm (
*https://github.com/vl4deee11/zidx*). I agree with the opinion that this z
algorithm is not suitable for std/strings. Later I will try to optimize and
write tests and benchmarks, follow this repository if someone is
interested.
Thanks to
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,
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:
> On Fri, Sep 17, 2021 at 12:03 PM vl4deee11 wrote:
> >
> > Yes, this algorithm is mainly
On Fri, Sep 17, 2021 at 12:03 PM vl4deee11 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
>
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
On Fri, Sep 17, 2021 at 8:38 AM vl4deee11 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
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 -