300iq's blog

By 300iq, 21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +59 Vote: I do not like it

u r very cute : )

»
21 month(s) ago, # |
  Vote: I like it +251 Vote: I do not like it

This is the worst story I have ever heard.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    You're just wrong. This is an amazing story.

    I love the use of symbolism! Please, quit competitive programming and become an author.

»
21 month(s) 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/

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

just great

»
21 month(s) ago, # |
  Vote: I like it +25 Vote: I do not like it

better than Twilight

»
21 month(s) ago, # |
  Vote: I like it +59 Vote: I do not like it

Cool story bro.

»
21 month(s) ago, # |
  Vote: I like it -16 Vote: I do not like it

I definitely need to work on my English.

»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it
»
21 month(s) 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

  • »
    »
    21 month(s) 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?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Maybe, but polynomial hashes should be enough.

»
21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Impressive.

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +204 Vote: I do not like it

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      • »
        »
        »
        »
        21 month(s) 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)

        • »
          »
          »
          »
          »
          21 month(s) 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

  • »
    »
    21 month(s) 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.