Manacher's Algorithm

June 13, 20222 min#string #palindrome #longest-palindrome #manacher

Table of Contents

There are multiple different ways of implementation for this problem, like DP(lcs, etc), expanding from center. But the most optimal approach is Manacher’s Algorithm, time complexity: O(n). It’s core idea is calculating current palindrome information based on previous calculated palindrome information. Let’s draw it and see some formulas and implications.

Some formulas & implications

To handle both even & odd lengths we need some preprocessing on string. It will be like this: ‘@#s#t#r#$’ There will be: n string chars + (n+1) ‘#’ symbol + 1 ‘@’ symbol + 1 ‘$’ symbol = 2n + 3 2n+3 => will be odd always

centerPos => is current center which expanded longer distance

note

Theorem

centerLeft + d = centerPos
centerRight - d = centerPos
centerLeft + centerRight = 2*centerPos
centerLeft + x = currentLeft (or mirror of currentRight)
x = d - i = centerRight - i
centerLeft + centerRight - i = currentLeft

tip

Key idea

Important implication: currentLeft (mirror) = 2*centerPos - i

But there could be two different cases:

warning

Watch out

currentLeft - distance[currentLeft] > centerLeft [it means it’s within borders of the centerLeft…centerPosition]
currentLeft - distance[currentLeft] < centerLeft [it means it’s out of borders of the centerLeft..centerPosition]

For the second case, we don’t know about the out of border information, therefore we need to cut until the border. [centerRight-currentLeft]

 1    def manachersSolve(self, s: str) -> str:
 2        # processing str = @#s#a#l#a#m#$
 3        newlen = 2*len(s) + 3
 4        newstr = ['@']
 5        newstr += [f'#{c}' for c in s]
 6        newstr += ['#$']
 7        newstr = ''.join(newstr)
 8        p = [0] * newlen
 9
10        maxlen = 0
11        centerPos = 0
12        centerLeftPos = 0
13        centerRightPos = 0
14
15        # centerRightPos - d = centerPos
16        # centerLeftPos + d = centerPos
17        # centerRightPos + centerLeftPos = 2*centerPos
18        # if centerPos + p[centerPos] > centerPos + i [inside]
19        # if centerPos + p[centerPos] < centerPos + i [outside]
20        # if centerPos - p[centerPos] < centerPos - i [inside]
21        # if centerPos - p[centerPos] > centerPos - i [outside]
22
23        for i in range(1, newlen-1):
24            if i < centerRightPos:
25                p[i] = min(centerRightPos-i, p[2*centerPos - i])
26
27            while (newstr[i-p[i]-1] == newstr[i + p[i] + 1]):
28                p[i] += 1
29
30            if (i + p[i] > centerRightPos):
31                centerPos = i
32                centerRightPos = centerPos + p[i]
33
34            if p[i] > maxlen:
35                start = (i-p[i]-1)//2
36                maxlen = p[i]
37
38        return s[start:start+maxlen]