Блог пользователя 300iq

Автор 300iq, 4 года назад, По-английски

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$$$.

  • Проголосовать: нравится
  • +324
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

u r very cute : )

»
4 года назад, # |
  Проголосовать: нравится +251 Проголосовать: не нравится

This is the worst story I have ever heard.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

like my story/

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

just great

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

better than Twilight

»
4 года назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Cool story bro.

»
4 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +69 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +42 Проголосовать: не нравится

    Impressive.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +204 Проголосовать: не нравится

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.