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.
>> Restart animation.
Built with D3.
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.
- Green point = presence of palindrome (single characters included).
- Red point = no palindrome.
- Gray points = space between characters.
>> Restart animation.
Built with D3.