How do I find the longest palindrome in a string? | Hacker News Reader

How do I find the longest palindrome in a string?

codegolf.stackexchange.com

31 pointsJoeCortopassi11 comments

For anyone interested in how to actually do this efficiently, without building a suffix tree, here's a good explanation: http://www.akalin.cx/longest-palindrome-linear-time

Cool, but unfortunately also a great example of when excessive commenting actually makes the code less digestible.

Right. A figure could be more intuitive. But the algorithm is tricky itself anyway...

In addition, the use of cryptic variable names like s, e, d or j with big block comments describing what each one stands for is particularly irritating.

Thanks for the feedback! In my defense, I can only say that I was a less-experienced coder when I wrote that. :)

The comments were intended to extend the preceding prose explanation rather than being comments per se. The actual code is not much longer than the naive version, though, so if I get around to writing an updated version, I'd probably find some other method of conveying that info.

Some other things I'd do differently if I were to update it today:

- I'd write it in Javascript and provide a little interactive applet to play with it. (Similar to my posts on primality testing: http://www.akalin.cx/intro-primality-testing and http://www.akalin.cx/primality-testing-polynomial-time-part-... .)

- I'd upload the code to GitHub.

- I'd add unit tests.

Cheers!

No offense was meant, no defense is necessary. Putting your code out there for HN to critique is indeed an admirable action. Your humility is even more admirable.

Your links on primality testing are particularly relevant to me as I just finished that section in SICP - thanks for the links!

"generate a set of every single possible Palindrome as large as the string you're testing"

This kind of memoization could well be the most efficient solution in the real world, albeit not one that will pass your CS 101 exam.

More generally #codetrolling is like putting the creative hat on and will probably help people to come up with out-of-the-box tricks that could in some cases be quite useful.

Wasnt this the old Cue/Greplin hiring challenge from years back?

Finally, a job for LISP.

suffix tree. same as longest subsequence problem. create suffix tree, reverse string and find longest subsequence.

Just search for "notlob".

Reply on news.ycombinator.com