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.

Հոլ

I bought an Armenian spinning top - Հոլ. You throw it, pull the string, and it starts to spin.

There is an interesting idea here from the physics point of view: the string starts unwinding when the radius is still big, and this is a good condition for starting the motion. Then, while the string unwinds, the radius decreases, giving you an opportunity to reach a high rotation speed.

I spent some time figuring out how to launch this toy. But once you can do it, it quickly becomes boring.

The next story is about how to make it fun again with colored discs, and what physiology is hiding behind these pictures.

The winners are...

The winners of yesterday quiz, of course, nine happy people who chose "Babbidi-bibidi-dup!" option. They are clearly happy!

But, If we are speaking about the truth behind the poll, the picture is much more intriguing. Three very inattentive people voted for the first and third options. It is a test for attention because the first and the third option are the same.

And finally. Who is right? A group of three inattentive people, or powerful unanimous group answered "two"?

The right options are the first and the third. With almost identical prompts chatgpt preferred to create fine-grained patters and claude - well organized solid structures.

It reminds me webs of spiders under psychoactive drugs.