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$$$.
u r very cute : )
This is the worst story I have ever heard.
once upon a time. there is a man, named palindrome.
like my story/
there was*
just great
better than Twilight
Cool story bro.
Link
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
No way! This "black box" thing seems really powerful! Do you think I may use prefix function as a black box here?
Maybe, but polynomial hashes should be enough.
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.
Impressive.
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.
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.
Context. Like, what else could he possibly have meant?
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)
Right! I guess the reason it seemed so obvious to me at the moment was that I was thinking the same thing :P
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.