tril0713's blog

A guess about strings: is it correct ?
By tril0713, 8 months ago, In English

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?

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I think YES I took some random cases and the answer did not exceed 5.

→ Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

deleted

→ Reply
»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe this will help?

→ Reply