What is Manacher’s Algorithm
In the fascinating world of string processing, there is a classic problem that has captivated countless algorithm enthusiasts: finding the longest palindromic substring in a string. A palindromic string is like a symmetrical artwork in the realm of strings, reading the same forwards and backwards, such as “level” or “madam”. The most straightforward approach to this problem is the brute-force method, which involves enumerating all substrings of the string and checking each substring to see if it is a palindrome, recording the longest one. However, this method has a time complexity of O(n³), making it extremely inefficient for larger strings. For example, for a string of length 1000, a vast number of substring checks would be required, resulting in a huge computational load and consuming a lot of time and resources.
Enter Manacher’s Algorithm, which provides a more efficient way to solve this problem. Proposed by Glenn K. Manacher in 1975, it can find the longest palindromic substring of a string in linear time O(n), significantly improving computational efficiency. This is akin to searching for a specific person in a crowd; the brute-force method is like asking each person one by one, while Manacher’s Algorithm is like having a map that allows you to find your target much faster, saving a great deal of time and effort. Next, let us delve into the principles and implementation of Manacher’s Algorithm.
Principle: How Manacher’s Algorithm Works
(1) Clever Preprocessing: Unifying Odd and Even Palindromes
The first step of Manacher’s Algorithm is to preprocess the original string. Since the length of a palindromic string can be odd (like “aba”) or even (like “abba”), this necessitates separate handling when searching for the center of the palindrome, increasing the complexity of the algorithm. To uniformly handle palindromes of both odd and even lengths, we insert a special character, here we choose “#”, before and after each character in the original string (any character not present in the original string would suffice).
For example, for the original string “aba”, after preprocessing it becomes “#a#b#a#”; for the original string “abba”, it becomes “#a#b#b#a#”. After this processing, the length of the new string is guaranteed to be odd, and all palindromic substrings also become odd in length. Thus, when searching for palindromes, we no longer need to distinguish between odd and even cases, greatly simplifying subsequent processing.
Moreover, the relationship between the radius of the palindromic substring in the processed string and the length of the corresponding palindromic substring in the original string is as follows: the radius of the palindrome centered at a certain character in the new string minus one equals the length of the corresponding palindromic substring in the original string. For instance, in the new string “#a#b#a#”, if the radius of the palindrome centered at “b” is 4, then the length of the palindromic substring centered at “b” in the original string “aba” is 4 – 1 = 3.
(2) Core Calculation: Solving the Palindrome Radius Array
After preprocessing, we begin to solve the palindrome radius array. Here we introduce two auxiliary variables: mx and id. mx represents the index of the rightmost boundary of the currently found palindromic substring (note that the character pointed to by mx does not belong to the palindrome); id represents the index of the center position of the palindromic substring corresponding to this rightmost boundary.
We also define an array p, where p[i] represents the radius of the palindrome centered at the i-th character of the new string (including the center character itself). Solving the p array is the core step of Manacher’s Algorithm, and we will analyze the calculation logic of p[i] in detail through a combination of diagrams and text.
Assuming we have already calculated the palindrome radii for the first i – 1 characters, we now need to calculate p[i]. At this point, we first find the symmetric point j of i with respect to id, that is, j = 2 * id – i. Due to the symmetry of palindromes, if the palindrome centered at j is within the palindrome centered at id, then there is a certain relationship between the palindrome centered at i and the one centered at j. There are three specific cases:
- 1. Case 1: When mx > i:
- • If p[j] < mx – i, this indicates that the palindrome centered at j is completely contained within the palindrome centered at id. Based on the symmetry of palindromes, the lengths of the palindromes centered at i and j are the same, so p[i] = p[j]. For example, for the string “#a#b#c#b#a#”, suppose the current id = 3, mx = 7, i = 5, j = 2 * 3 – 5 = 1. If p[1] = 2 and 2 < 7 – 5, then p[5] = 2.
- • If p[j] >= mx – i, this means that the palindrome centered at j is not completely contained within the palindrome centered at id. However, based on symmetry, we can determine that the palindrome centered at i can at least extend to the position of mx, that is, p[i] = mx – i. As for whether the part beyond mx is symmetric, we need to start checking from the position mx + 1, matching character by character to determine. For example, for the string “#a#b#c#c#b#a#”, suppose id = 3, mx = 7, i = 5, j = 1. If p[1] = 4 and 4 >= 7 – 5, then p[5] = 7 – 5 = 2. Then we continue checking for symmetry starting from mx + 1 (i.e., position 8); if symmetric, p[5] continues to increase.
- 1. Case 2: When mx <= i:
At this point, we cannot use the information from previous palindromes to quickly determine p[i], and can only start from position i, using the center expansion method to expand character by character to determine the radius of the palindrome centered at i, initializing p[i] to 1, and continuously checking if s[i – p[i]] equals s[i + p[i]]. If they are equal, p[i] increases. For example, for the string “#a#b#d#”, when i = 4, mx may be less than or equal to 4, at which point we start from position 4, checking if “#” equals “#” (here we assume s[0] and s[8] are the special characters added at both ends of the string to ensure no out-of-bounds), and if they are equal, p[4] increases, continuing to check the next pair of characters until they are not equal.
Through the above steps, we can gradually calculate all elements in the p array. Finally, we find the maximum radius value in the p array, and the corresponding palindromic substring is the longest palindromic substring of the original string. For example, for the string “#a#b#c#b#a#”, the calculated p array might be [1, 2, 1, 4, 1, 2, 1], where the maximum radius is 4, corresponding to the longest palindromic substring “#b#c#b#”. After removing the “#”, the longest palindromic substring of the original string is “bcb”.
Rust Implementation of Manacher’s Algorithm
Below is the code for implementing Manacher’s Algorithm in Rust, and we will analyze the code line by line in conjunction with the principles discussed earlier.
pub fn manacher(s: String) -> String {
let l = s.len();
if l <= 1 {
return s;
}
// Create a mutable character vector `chars` and preallocate enough capacity, which is twice the length of the original string plus one.
// Then iterate through each character of the original string `s`, inserting a special character `#` before each character, and finally insert another `#` at the end of the new string.
// For example, if the original string is "abc", it becomes "#a#b#c#" after processing. This way, all palindromic substrings have odd lengths, facilitating subsequent uniform processing.
let mut chars: Vec<char> = Vec::with_capacity(s.len() * 2 + 1);
for c in s.chars() {
chars.push('#');
chars.push(c);
}
chars.push('#');
// `length_of_palindrome`: a mutable vector used to store the radius of the palindrome centered at each character, initialized to 1. Here, a radius of 1 indicates a palindrome that only contains the character itself.
// `current_center`: the index of the center position of the currently checked palindrome.
// `right_from_current_center`: the index of the right boundary of the currently checked palindrome (excluding that character).
let mut length_of_palindrome = vec![1usize; chars.len()];
let mut current_center: usize = 0;
let mut right_from_current_center: usize = 0;
// Core calculation loop
for i in 0..chars.len() {
// 1. Check if the current position is in the right half of the palindrome. This is used to determine whether the character being processed is in the right half of the palindrome.
if right_from_current_center > i && i > current_center {
/**
* If the condition is met, copy the value from the left side.
* If the current value plus the index exceeds the right boundary index, it needs to be truncated and checked for the palindrome later (see #3).
*/
length_of_palindrome[i] = std::cmp::min(
right_from_current_center - i,
length_of_palindrome[2 * current_center - i],
);
// 1-2: Check if the palindromic substring exceeds the right boundary; if it does, move to the new index position.
// This ensures that the palindrome expansion check always stays within a valid range.
if length_of_palindrome[i] + i >= right_from_current_center {
current_center = i;
right_from_current_center = length_of_palindrome[i] + i;
/**
* When the radius exceeds the end of the list, it indicates that the check is complete.
* Since the string will only get shorter, no larger value will be obtained.
*/
if right_from_current_center >= chars.len() - 1 {
break;
}
} else {
/**
* If the checked index does not exceed the right boundary, it indicates that the length is the same as the left side,
* and no further checks are needed.
*/
continue;
}
}
/**
* The radius value of the currently checked index.
* If this value is copied from the left side and is greater than 1, it indicates that it is ensured that no checks are needed within the radius.
*/
let mut radius: usize = (length_of_palindrome[i] - 1) / 2;
radius += 1;
/**
* Check if the given input is a palindrome.
* Note: Need to handle potential `usize` overflow issues.
*/
while i >= radius && i + radius <= chars.len() - 1 && chars[i - radius] == chars[i + radius]
{
length_of_palindrome[i] += 2;
radius += 1;
}
}
// 3: Find the maximum length and generate the answer.
let center_of_max = length_of_palindrome
.iter()
.enumerate()
.max_by_key(|(_, &value)| value)
.map(|(idx, _)| idx)
.unwrap();
let radius_of_max = (length_of_palindrome[center_of_max] - 1) / 2;
let answer = &chars[(center_of_max - radius_of_max)..(center_of_max + radius_of_max + 1)]
.iter()
.collect::<string>();
return answer.replace("#", "");
}</string>Application Scenarios
Although Manacher’s Algorithm is primarily used to find the longest palindromic substring, it has a wide range of applications in practical projects, demonstrating its powerful utility.
In the field of cryptography, detecting palindromic structures in encrypted strings can help assess the security of the encryption. Some simple encryption algorithms may inadvertently produce palindromic structures, which, if discovered by attackers, could become a breakthrough point for cracking the password. For example, in certain transposition ciphers, due to the nature of the transposition rules, some ciphertext may form palindromes. Using Manacher’s Algorithm to quickly detect palindromic substrings in ciphertext can help identify potential vulnerabilities in the encryption process, allowing for timely improvements to enhance the security of the cryptographic system.
In text processing, Manacher’s Algorithm can also play an important role. In text similarity assessment, by finding the longest palindromic substring in two texts, we can measure their similarity from a unique perspective. If two texts have the same or similar longest palindromic substrings at certain key positions, they are likely to have some semantic or structural correlation. For instance, in plagiarism detection, if two articles contain the same longer palindromic substring, it may suggest the presence of plagiarism. In spell-checking, Manacher’s Algorithm can also shine. Suppose we have a correct text database; for the text to be checked, by finding its longest palindromic substring and comparing it with the corresponding palindromic substring in the database, if significant differences are found, there may be a typo. For example, if a palindromic substring in the correct text is “level”, but the corresponding position in the text to be checked is “levl”, this is likely a typo that needs further inspection and correction.
(Note: The above application scenarios are sourced from online statistics.)
Conclusion
Manacher’s Algorithm cleverly reduces the time complexity of finding the longest palindromic substring to O(n) through preprocessing and utilizing the symmetry of palindromes. Its implementation in Rust fully demonstrates its efficiency and operability. It has a wide range of applications in cryptography, text processing, and more, providing strong support for solving practical problems.
If you are interested in string processing algorithms, you can also explore the KMP algorithm, BM algorithm, and others, which have unique advantages in string matching and other areas. The world of algorithms is rich and colorful; every deep exploration may bring new insights and discoveries. I hope everyone continues to advance on the path of learning algorithms and uncover more exciting aspects!
(Note: The above is a personal opinion; everyone is welcome to discuss in the comments section.)
Can Rust implement Nginx proxy?Rust Practice: Combining Axum with Database for Efficient Web Development