LeetCode Solution: Manacher's Algorithm for Longest Palindromic String
Manacher, commonly known as the 马拉车 (Malache) algorithm, is the protagonist of this article. It is an efficient algorithm that can reduce the time complexity of solving the longest palindromic string problem to O(N). When I first encountered problems asking for the longest palindromic string, I initially used the brute force approach - traversing all possible substrings with O(N²) complexity, then using O(N) time to find the maximum palindrome length. Although using a map to store palindrome information for various index pairs could reduce some calculations, this approach clearly had too high time complexity and was prone to timeout issues for certain test cases.
The general idea of this algorithm is as follows:
- Simplify odd/even number considerations and boundary interference for palindrome judgment by inserting special symbols
- The half of the entire boundary (excluding the center point) of the center point exactly equals the maximum palindromic string length at the center point
- Utilize the symmetry rule of maximum palindromic substrings within large palindromic boundaries to greatly simplify calculations
I implemented the above algorithm using Go language. The detailed code is as follows:
// LeetCode No.5 Longest Palindromic Substring
func longestPalindrome(s string) string {
// Convenient for us to directly use slice operations to get results later
origin := []byte(s)
// A single character doesn't need palindrome consideration
if len(origin) == 1 {
return s
}
var maxCenterIndex int
bs := process(s)
p := make([]int, len(bs))
c := 0
r := 0
for i:=1;i<len(bs)-1;i++{
// mirror is the symmetric index of i with c as the axis of symmetry
mirror := 2*c-i
// When there is a right boundary
if r > i {
// When the boundary doesn't exceed the maximum palindromic string length of the large palindromic string center, it equals the maximum palindromic string length at the symmetric position
if r-i > p[mirror] {
p[i] = p[mirror]
} else {
// When the boundary exceeds, the minimum maximum palindromic string length at position i equals the length from i to the boundary
p[i] = r-i
}
}
// Calculate the maximum palindromic string length at position i. Previous steps of calculating p[i] save a lot of palindrome comparisons
// Note +1 and -1 to exclude the comparison of a character with itself
for bs[p[i]+i+1] == bs[i-p[i]-1] {
p[i]++
}
// Recalculate the center when the boundary expands
if i+p[i] > r {
r = i+p[i]
c = i
}
// Each round of calculation gets the maximum palindromic string length centered at bs[i], here we maintain the maximum one
if p[maxCenterIndex] < p[i] {
maxCenterIndex = i
}
}
mx := p[maxCenterIndex]
// Calculate the starting position of the source string from the center position of the intermediate string
startIndex := (maxCenterIndex - 1) / 2 - mx/2
endIndex := startIndex + mx
return string(origin[startIndex:endIndex])
}
// Use buffer to efficiently process the original string, aiming to handle problems caused by odd/even numbers and boundaries in the original string, making the algorithm implementation more concise
// eg: input - "abcabc" -> output - "^#a#b#c#a#b#c#$"
// ps: Go 1.10 version already supports stringBuilder
func process(s string) []byte {
bs := []byte(s)
var buffer bytes.Buffer
buffer.WriteString("^")
for _,b := range bs {
buffer.WriteString("#")
buffer.WriteByte(b)
}
buffer.WriteString("#$")
return buffer.Bytes()
}Views