Create viral videos with

GPT-4o + Ads library

Use GPT-4o to edit video empowered by Youtube & Tiktok & Facebook ads library. Turns your links or media assets into viral videos in one click.

Try it free

#Education

Hello everyone, today I'm going to explain a semi-niche algorithm called Manacher's algorithm. This algorithm can be used to find the longest palindrome in a string, count the number of palindromes of a certain length in a string, and more. It's also an introductory string algorithm that's relatively simple and can serve as a stepping stone to more complex algorithms. Let's get started!

The aim of Manacher's algorithm is to calculate the length of the longest palindrome centered around each character in a string. For coding simplicity, instead of storing the actual lengths, we store the distance from the center of the palindrome to its boundary. For example, if the longest palindrome centered around a character 'B' is "CBC", the output array will store the number 2 for 'B' because the palindrome stretches out two characters in either direction.

Example:

```
Input String: "abbcbba"
Output Array: [1, 2, 3, 2, 1, 0, 0]
```

A naive approach would involve initializing the length around each character to 1 and expanding outwards while checking that the expanding characters are equal. This naïve approach leads to an O(n²) worst-case runtime.

Example of Naive Approach:

```
Input String: "aaaa"
Output Array: [1, 2, 3, 4]
```

Manacher's algorithm optimizes this process to run in O(n) time by leveraging previously computed palindromes and their properties.

**Initialization**:`int len[n] = (0); int c = 0, r = 0; // c is the center of the current rightmost palindrome, r is its boundary`

**Processing Each Character**:`for (int i = 0; i < n; i++) ( // Mirror index int mirror = 2 * c - i; // Initialize length if (r > i) len[i] = min(r - i, len[mirror]); // Center Expansion while (i + len[i] + 1 < n && i - len[i] - 1 >= 0 && s[i + len[i] + 1] == s[i - len[i] - 1]) { len[i]++; ) // Update right boundary if needed if (i + len[i] > r) ( c = i; r = i + len[i]; ) }`

**Using a Modified String**:- Suppose the original string is "abba". Convert it to a format with boundary markers for easier handling:
`"abbab"`

, you convert to`"#a#b#b#a#"`

.

- Suppose the original string is "abba". Convert it to a format with boundary markers for easier handling:
**Extracting the Longest Palindrome**:- After constructing the
`len`

array, the maximum value indicates the length of the longest palindrome.

- After constructing the
**Final Implementation**:`string preprocess(const string& s) ( string t = "#"; for (char c : s) t += c + "#"; return t; ) string manacherLongestPalindrome(const string& s) ( string t = preprocess(s); int n = t.size(), c = 0, r = 0; vector<int> len(n, 0); for (int i = 0; i < n; i++) { int mirror = 2 * c - i; if (r > i) len[i] = min(r - i, len[mirror]); while (i + len[i] + 1 < n && i - len[i] - 1 >= 0 && t[i + len[i] + 1] == t[i - len[i] - 1]) { len[i]++; ) if (i + len[i] > r) ( c = i; r = i + len[i]; ) } int maxLen = 0, centerIndex = 0; for (int i = 0; i < n; i++) ( if (len[i] > maxLen) { maxLen = len[i]; centerIndex = i; ) } int start = (centerIndex - maxLen) / 2; return s.substr(start, maxLen); }`

The algorithm runs in linear time because, for each character in the string, the while loop inside the main loop can increment the right boundary only once. The comparison of the palindrome boundaries results in constant time operations overall, leveraging the properties of the palindrome centered at the other side.

After coding the algorithm, it was tested on the CSES "Longest Palindromic Substring" problem and functioned correctly. All test cases were resolved in 0.04 seconds, showing the efficiency of the implementation.

For further exploration, the Z-Algorithm, which has a similar optimization concept, will be discussed next time. The Z-Algorithm works on finding pattern matches efficiently by maintaining rightmost structures and leveraging their properties.

- Manacher's Algorithm
- String Processing
- Palindromes
- Algorithm Optimization
- Linear Time Complexity

**What is Manacher's Algorithm used for?**- It is used to find the longest palindrome in a string, count palindromes of a specific length, and more.

**How does Manacher's Algorithm work?**- It calculates the length of the longest palindrome centered at each character by utilizing memoized information about previous palindromes and leveraging symmetrical properties around a center.

**Why is Manacher's Algorithm optimal for finding palindromes?**- The algorithm runs in O(n) time because it optimizes the expansion check process by using previously computed palindromic lengths.

**What kind of pre-processing is required for Manacher's Algorithm?**- The input string is modified by inserting boundary markers to handle odd and even length palindromes uniformly.

**Can Manacher's Algorithm be adapted for other languages?**- Yes, the principles of the algorithm can be adapted to any programming language, maintaining its efficiency and correctness.

In addition to the incredible tools mentioned above, for those looking to elevate their video creation process even further, Topview.ai stands out as a revolutionary online AI video editor.

TopView.ai provides two powerful tools to help you make ads video in one click.

Materials to Video: you can upload your raw footage or pictures, TopView.ai will edit video based on media you uploaded for you.

Link to Video: you can paste an E-Commerce product link, TopView.ai will generate a video for you.

You may also like