We call a string $$$s$$$ of length $$$n$$$ good, if and only if $$$n \bmod 2 = 0$$$ and $$$s[1,\dfrac{n}{2}] = s[\dfrac{n}{2}+1,n]$$$ (i.e. there exists a string $$$t$$$ that $$$s = t + t$$$.)
You are given a string $$$s$$$. For each $$$r \in [1,n]$$$:
- Find all good substrings ending at position $$$r$$$.
- The guess is: Their length can be divided into $$$\mathcal O(\log n)$$$ consecutive intervals.
Is the guess correct?
I think YES I took some random cases and the answer did not exceed 5.
OMG Why I am downvoted?
deleted
What do you mean by consecutive intervals? Their lengths can only be even.
If you mean consecutive when we only look at even values, then this fails if the string is "abcd" repeated.
Also, if both $$$l, l+2$$$ are good lengths for a fixed $$$r$$$, then so is every even length from $$$2$$$ to $$$l+2$$$. Which means the consecutive intervals are only $$$2[1, k]$$$ and other singletons, so idk why it would be logarithmic.
Did I get the question correctly?
Yes You get the question correctly and thanks a lot.
I came up with the guess by thininkng "the length will increase a lot or increase 1 from a good string to a longer good string", but a didn't consider strings like $$$\texttt{abcdabcdabcd}$$$ …
Now there is another guess: their lengths can be divided into $$$\mathcal O(\log n)$$$ arithmetic progressions
Is it correct now ? Thank you again
Maybe this will help?