Find the longest palindrome in "abacabad". A palindrome can have an even or an odd length, and that is two cases nobody wants to write twice, so put a # in every gap and at both ends: "#a#b#a#c#a#b#a#d#". Every palindrome in there is now odd, centred on one position, and its radius is exactly the length of the palindrome in the original text.
Manacher over 17 transformed positions.
Position 1 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 1 is outside the box. Starting radius 0.
Each comparison one step further out matches, 1 time, so the radius at 1 grows to 1, which is the palindrome "a" in the original text. It reaches further right than the old box, so the box moves to centre 1, right edge 2.
Radius at 1 is 1.
Position 2 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 2 is outside the box. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 2 stays 0.. The box is unchanged.
Radius at 2 is 0.
Position 3 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 3 is outside the box. Starting radius 0.
Each comparison one step further out matches, 3 times, so the radius at 3 grows to 3, which is the palindrome "aba" in the original text. It reaches further right than the old box, so the box moves to centre 3, right edge 6.
Radius at 3 is 3.
Position 4 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.
Position 4 mirrors 2. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 4 stays 0.. The box is unchanged.
Radius at 4 is 0.
Position 5 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 1, with radius 1. The mirror can be copied, but only as far as the box reaches: 1. So the starting radius is the smaller of the two, 1.
Position 5 mirrors 1. Starting radius 1.
Comparing the characters one step out fails immediately, so the radius at 5 stays 1., which is the palindrome "a" in the original text. The box is unchanged.
Radius at 5 is 1.
Position 6 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 6 is outside the box. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 6 stays 0.. The box is unchanged.
Radius at 6 is 0.
Position 7 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 7 is outside the box. Starting radius 0.
Each comparison one step further out matches, 7 times, so the radius at 7 grows to 7, which is the palindrome "abacaba" in the original text. It reaches further right than the old box, so the box moves to centre 7, right edge 14.
Radius at 7 is 7.
Position 8 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 6, with radius 0. The mirror can be copied, but only as far as the box reaches: 6. So the starting radius is the smaller of the two, 0.
Position 8 mirrors 6. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 8 stays 0.. The box is unchanged.
Radius at 8 is 0.
Position 9 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 5, with radius 1. The mirror can be copied, but only as far as the box reaches: 5. So the starting radius is the smaller of the two, 1.
Position 9 mirrors 5. Starting radius 1.
Comparing the characters one step out fails immediately, so the radius at 9 stays 1., which is the palindrome "a" in the original text. The box is unchanged.
Radius at 9 is 1.
Position 10 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 4, with radius 0. The mirror can be copied, but only as far as the box reaches: 4. So the starting radius is the smaller of the two, 0.
Position 10 mirrors 4. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 10 stays 0.. The box is unchanged.
Radius at 10 is 0.
Position 11 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 3, with radius 3. The mirror can be copied, but only as far as the box reaches: 3. So the starting radius is the smaller of the two, 3.
Position 11 mirrors 3. Starting radius 3.
Comparing the characters one step out fails immediately, so the radius at 11 stays 3., which is the palindrome "aba" in the original text. The box is unchanged.
Radius at 11 is 3.
Position 12 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.
Position 12 mirrors 2. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 12 stays 0.. The box is unchanged.
Radius at 12 is 0.
Position 13 sits inside the palindrome centred at 7, which reaches index 14. Its mirror image about 7 is position 1, with radius 1. The mirror can be copied, but only as far as the box reaches: 1. So the starting radius is the smaller of the two, 1.
Position 13 mirrors 1. Starting radius 1.
Comparing the characters one step out fails immediately, so the radius at 13 stays 1., which is the palindrome "a" in the original text. The box is unchanged.
Radius at 13 is 1.
Position 14 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 14 is outside the box. Starting radius 0.
Comparing the characters one step out fails immediately, so the radius at 14 stays 0.. The box is unchanged.
Radius at 14 is 0.
Position 15 is outside the rightmost palindrome found so far, so there is nothing to copy: start from radius 0 and compare.
Position 15 is outside the box. Starting radius 0.
Each comparison one step further out matches, 1 time, so the radius at 15 grows to 1, which is the palindrome "d" in the original text. It reaches further right than the old box, so the box moves to centre 15, right edge 16.
Radius at 15 is 1.
The largest radius is 7 at position 7, which is the palindrome "abacaba" starting at index 0 of the original text. Every position was visited once and the right edge of the box only ever moves forward, so the 27 character comparisons are O(n) in total: the mirror is what turns the obvious O(n^2) expansion into linear time.
The longest palindrome is abacaba, length 7.