300iq's blog

Short story about palindromes
By 300iq, 5 years ago, In English

You are given a string $$$s$$$, and for each $$$r$$$ you need to find the largest $$$L_r$$$, such that $$$s[r - L_r + 1 \ldots r]$$$ is a palindrome.

It is possible to solve this problem with the eertree or with Manacher's algorithm with some data structures, but I will describe a simpler way.

You will need some black box, that for any substring $$$s[l \ldots r]$$$ can check in $$$\mathcal{O}{(1)}$$$ if it is a palindrome. The easiest such black box is a polynomial hash, but also you can precalculate stuff from Manacher's algorithm and then check that $$$\frac{(l+r)}{2}$$$ is a middle of a long enough palindrome.

The key fact here is that $$$L_i \leq L_{i-1} + 2$$$, because if $$$s[l \ldots r]$$$ is a palindrome, then $$$s[l+1 \ldots r-1]$$$ is a palindrome too.

With this observation, we can use our black box to find the required values!

Let's assume that you already know $$$L_1, L_2, \ldots, L_{i-1}$$$ and we want to calculate $$$L_i$$$.

Starting from $$$L_i = L_{i-1}+2$$$, decrease $$$L_i$$$ while $$$s[i - L_i + 1 \ldots i]$$$ is not a palindrome.

The number of black box operations of this algorithm is $$$\sum{(L_{i-1} + 2 - L_i)}$$$ $$$\leq 2 n$$$.

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

Comments Comments (20)
| Write comment?
»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

u r very cute : )

→ Reply
»
5 years ago, # |
  Vote: I like it +251 Vote: I do not like it

This is the worst story I have ever heard.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

once upon a time. there is a man, named palindrome.

like my story/

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

just great

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

better than Twilight

→ Reply
»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Cool story bro.

→ Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Link

→ Reply
»
5 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Don't tell anybody, but I've heard that it's also possible to calculate the length of the longest border of each prefix of the string in a linear time :o

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    No way! This "black box" thing seems really powerful! Do you think I may use prefix function as a black box here?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Maybe, but polynomial hashes should be enough.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +69 Vote: I do not like it

And to further simplify this algorithm (that is, to make your "black box" built-in) you may store for each prefix the length of its second largest $$$L_r$$$ and also the position in which $$$s[r-L_r+1...r]$$$ occurs for the first time. In this way you may traverse suffix-palindromes of $$$s[1...i-1]$$$ only. Seems simple and resembles prefix-function, right? Yeah, except that it's exactly eertree.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Impressive.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    On one hand I understand your point, on the other I seriously doubt this is "further simplifying" with some suffix-links and shit and I think version from blog is really simple to understand and remember and has some value in itself as such.

    → Reply
»
5 years ago, # |
  Vote: I like it +204 Vote: I do not like it

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Up to this day I am wondering how some people apparently understood what he meant even though he dropped whole "what would happen" in the middle of this sentence.

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

      Context. Like, what else could he possibly have meant?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        For me it was quite obvious that what he meant was ... "I am only wondering if such post has been made by green or grey" xdd. Doesn't this sentence already have well defined meaning xd? Shedding some more light — implying that post this referred to was so low quality it must have been authored by either green or grey but author of this comment doesn't know which is the case (meant of course as humorous mocking the author)

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Right! I guess the reason it seemed so obvious to me at the moment was that I was thinking the same thing :P

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

    I don't get it. Maybe nik7 had a point about the escape room post (though I'd say it is arguable, I'd say the comment is kinda irrelevant). But would a green or grey posting this really make a difference.

    → Reply