Manacher superpowers
These days you are either getting work done or keeping up with contemporary technologies - rarely both. You know, we are living in a strange time. There is an information bubble around agentic programming, and people do crazy things in there. I'm officially out of this race, and I try to stay somewhere in the middle of the bubble — not to spend tons of time on chasing new technologies, but to give a chance to some of them from time to time.
Today two of my vectors of interest became collinear: algorithms and the superpowers skill. Once in a while I'm refreshing some algorithms, and stringology is one of the themes that always slips out of my mind. In the post we discussed the quadratic algorithm for finding the longest palindrome, then I wanted to recall Manacher, which works in T=O(n). That's the kind of skill that lets you build strong features. I decided to try both and created this page.
My old-school self-education approach was to recall the idea, then play with a piece of paper and a pencil, trying to convert the main idea into code. This time I opened Claude in the console, added the superpowers plugin, described the site, and in a few iterations got it. Here you can check the main purpose of this algorithm — finding the longest palindrome in a string, the complexity estimates of the naive O(n*n) and the Manacher O(n) algorithms, the algorithm description, implementations in several languages, and several approaches to implementation.
I keep thinking about Gödel when writing string algorithms like Knuth-Morris-Pratt or Manacher. Because the main trick in them is the "self-reference" property. In KMP you jump to a substring which is a substring of your current substring. In the Manacher algorithm we use the symmetry of the answer, which is inherited from the input data. Namely, if you have a big palindrome "abaCabaDabaCaba", you keep track of the lengths of palindromic substrings, and once you have filled the left part of this array, you can take the already-calculated values as a good approximation for the current value of your array. Wow. It seems I really started to recall this algorithm, and there is a chance that from here on I can start playing with pen and paper.
I'll try to come up with a nice explanation of this algorithm. Meanwhile, feel free to play with the webpage.