### 300iq's blog

By 300iq, 4 years ago,

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

| Write comment?
 » 4 years ago, # |   +59 u r very cute : )
 » 4 years ago, # |   +251 This is the worst story I have ever heard.
 » 4 years ago, # |   +3 once upon a time. there is a man, named palindrome.like my story/
•  » » 4 years ago, # ^ | ← Rev. 2 →   +4 there was*
 » 4 years ago, # |   0 just great
 » 4 years ago, # |   +25 better than Twilight
 » 4 years ago, # |   +59 Cool story bro.
 » 4 years ago, # |   +32
 » 4 years ago, # |   +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 years ago, # ^ |   +31 No way! This "black box" thing seems really powerful! Do you think I may use prefix function as a black box here?
•  » » » 4 years ago, # ^ |   +14 Maybe, but polynomial hashes should be enough.
 » 4 years ago, # | ← 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 years ago, # ^ |   +42 Impressive.
•  » » 4 years ago, # ^ |   +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 years ago, # |   +204
•  » » 4 years ago, # ^ |   +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 years ago, # ^ |   +8 Context. Like, what else could he possibly have meant?
•  » » » » 4 years ago, # ^ |   +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 years ago, # ^ |   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 years ago, # ^ |   +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.