Taro Kuriyama

Palindromes I

This visualization illustrates an algorithm to find the longest palindromic substring within a given string (e.g. "noon" within "it is noontime").

The algorithm in this example is suboptimal but simple, with a worst-case complexity of \(O(n^2)\) in the case of a string comprising the same repeated character. For most natural language examples, it runs closer to \(O(n)\).

Each character and the space between each character is considered as the center of a possible palindrome. From each center, the algorithm checks whether the two adjacent characters (i.e. to the left and right) match. If they match, the algorithm examines the next pair of adjacent characters. This is repeated until no match is found, at which point the next center is considered.

The visualization traces the algorithm path as the string is scanned from left to right. The longest palindromic substring is identified by two green points on the x axis with the greatest distance between them. A larger example ("amanaplanacanalpanama") is available here.

>> Restart animation.

Built with D3.