Manacher算法

Manacher算法用于查找给定字符串中的最长回文子串。回文是指与自身反转相等的字符串，回文子串是指也是回文的字符串的子串，例如“aabaaccaabaa”中的“aabaa”。该算法由Glenn K. Manacher于1975年提出。

Manacher算法是如何工作的？

查找最长回文子串的朴素方法是检查给定字符串的每个可能的子串，然后验证它是否为回文。但是，这将消耗更多的时间和空间。

Manacher算法通过利用一些观察和技巧，以线性时间，即O(n)，解决了这个问题。主要思想是利用回文的对称性来避免不必要的比较。

算法

Manacher算法涉及以下步骤：

首先，我们通过在每对字符之间以及字符串的开头和结尾插入一个特殊字符（例如“#”）来预处理给定的字符串。这确保了新字符串中的每个回文都具有奇数长度和唯一的中心。例如，字符串“abba”变为“#a#b#b#a#”。
接下来，我们创建一个名为P[]的数组，其长度与新字符串相同，其中P[i]存储以新字符串中位置i为中心的回文子串的最长长度。我们初始化P[0] = 0和P[1] = 1，因为前两个字符始终是单字符回文。
然后，我们从左到右遍历新字符串。
对于每个位置i，找到i相对于当前最右回文中心的镜像位置j。
接下来，将P[j]的值复制到P[i]，除非它超过边界R。
通过比较i + P[i]两侧的字符来扩展以i为中心的回文。如果它们匹配，我们将P[i]增加1并重复此步骤，直到它们不匹配或到达字符串的末尾。

示例

在下面的示例中，我们将实际演示Manacher算法如何在各种编程语言中工作。

C C++ Java Python

#include<stdio.h>
#include<string.h>
// Function to return the minimum of two integers
int minm(int a, int b) {
   return (a<b)?a:b;
}
// Function to find longest palindromic substring
void findLongPalindrome(char orgnlString[]) {
   int n = strlen(orgnlString);
   if(n == 0)
      // If the string is empty, return an empty string
      return;
   n = 2*n + 1;
   // Array to store the length of palindrome 
   int lenPalndrm[n];
   // Initialization of first two positions
   lenPalndrm[0] = 0; lenPalndrm[1] = 1;
   int centerIndex = 1;
   int rightIndex = 2;
   int right = 0, left;
   int maxPalLength = 0, maxCenterIndex = 0;
   int start = -1, end = -1, diff = -1;
   // Loop through the string
   for (right = 2; right < n; right++) {
      left  = 2*centerIndex-right;
      lenPalndrm[right] = 0;
      diff = rightIndex - right;
      // If difference is greater than 0, update length at current position
      if(diff > 0)
         lenPalndrm[right] = minm(lenPalndrm[left], diff);
      // While the palindrome can be extended, extend it   
      while ( ((right + lenPalndrm[right]) < n && (right - lenPalndrm[right]) > 0) &&
         ( ((right + lenPalndrm[right] + 1) % 2 == 0) ||
         (orgnlString[(right + lenPalndrm[right] + 1)/2] == orgnlString[(right - lenPalndrm[right] - 1)/2] ))) {
         lenPalndrm[right]++;
      }
      // If the palindrome length at the current position is greater than the maximum palindrome length, update the maximum palindrome length and its center index
      if(lenPalndrm[right] > maxPalLength) {
         maxPalLength = lenPalndrm[right];
         maxCenterIndex = right;
      }
      // If the right boundary of the palindrome at the current position is greater than the right index, update the center index and the right index
      if (right + lenPalndrm[right] > rightIndex) {
         centerIndex = right;
         rightIndex = right + lenPalndrm[right];
      }
   }
   start = (maxCenterIndex - maxPalLength)/2;
   end = start + maxPalLength - 1;
   // maximum palindrome
   char maxPalindrm[end-start+2];
   strncpy(maxPalindrm, &orgnlString[start], end-start+1);
   maxPalindrm[end-start+1] = '\0';
   printf("Longest palindrome is: %s\n", maxPalindrm);
}
int main() {
   char orgnlString[] = "AAAABCAEAAABCBDDAAAAABC";
   // method calling
   findLongPalindrome(orgnlString);
   return 0;
}

#include<iostream> 
using namespace std; 
// Function to return the minimum of two integers
int minm(int a, int b) {
   return (a<b)?a:b; 
}
// Function to find longest palindromic substring 
string findLongPalindrome(string orgnlString) {
   int n = orgnlString.size(); 
   if(n == 0)
      // If the string is empty, return an empty string
      return ""; 
   n = 2*n + 1; 
   // Array to store the length of palindrome 
   int lenPalndrm[n]; 
   // Initialization of first two positions
   lenPalndrm[0] = 0; lenPalndrm[1] = 1; 
   int centerIndex = 1; 
   int rightIndex = 2; 
   // Variables to store the current right and left positions
   int right = 0, left; 
   // Variables to store maximum palindrome length and its center index
   int maxPalLength = 0, maxCenterIndex = 0; 
   int start = -1, end = -1, diff = -1; 
   // Loop through the string
   for (right = 2; right < n; right++) {
      // Calculate the corresponding left position
      left  = 2*centerIndex-right; 
      lenPalndrm[right] = 0; 
      diff = rightIndex - right; 
      // If difference is greater than 0, update length at current position
      if(diff > 0)
         lenPalndrm[right] = min(lenPalndrm[left], diff);
      // While the palindrome can be extended, extend it
      while ( ((right + lenPalndrm[right]) < n && (right - lenPalndrm[right]) > 0) &&
         ( ((right + lenPalndrm[right] + 1) % 2 == 0) ||
         (orgnlString[(right + lenPalndrm[right] + 1)/2] == orgnlString[(right - lenPalndrm[right] - 1)/2] ))) {
         lenPalndrm[right]++;
      }
      // If the palindrome length at the current position is greater than the maximum palindrome length, update the maximum palindrome length and its center index
      if(lenPalndrm[right] > maxPalLength) {    
         maxPalLength = lenPalndrm[right];
         maxCenterIndex = right;
      }
      // If the right boundary of the palindrome at the current position is greater than the right index, update the center index and the right index
      if (right + lenPalndrm[right] > rightIndex) {
         centerIndex = right;
         rightIndex = right + lenPalndrm[right];
      }
   }
   // Calculate the start and end indices of the maximum palindrome
   start = (maxCenterIndex - maxPalLength)/2;
   end = start + maxPalLength - 1;
   string maxPalindrm; 
   // Construct the maximum palindrome
   for(int i=start; i<=end; i++)
      maxPalindrm += orgnlString[i];
      // Returning maximum palindrome
      return maxPalindrm; 
}
int main(int argc, char *argv[]) {
   string orgnlString, palindrome;
   orgnlString = "AAAABCAEAAABCBDDAAAAABC";
   // method calling
   palindrome = findLongPalindrome(orgnlString); 
   cout << "Longest palindrome is: " << palindrome << endl; 
}

import java.util.Arrays;
public class Main {
   // Function to find longest palindromic substring
   public static String findLongestPalindrome(String orgnlString) {
      // If the string is null or empty, return an empty string
      if (orgnlString == null || orgnlString.length() == 0) 
         return "";
      char[] s2 = addBoundaries(orgnlString.toCharArray()); 
      // Array to store the length of palindrome
      int[] lenPlandrm = new int[s2.length]; 
      int centerIndex = 0, right = 0; 
      // to compare if two elements are the same
      int m = 0, n = 0;
      // Loop through the string
      for (int i = 1; i<s2.length; i++) {
         if (i > right) {
            lenPlandrm[i] = 0; m = i - 1; n = i + 1;
         } else {
            int i2 = centerIndex * 2 - i;
            if (lenPlandrm[i2] < (right - i - 1)) {
               lenPlandrm[i] = lenPlandrm[i2];
               m = -1;  
            } else {
                lenPlandrm[i] = right - i;
                n = right + 1; m = i * 2 - n;
            }
         }
         // While the palindrome can be extended, extend it
         while (m >= 0 && n < s2.length && s2[m] == s2[n]) {
            lenPlandrm[i]++; m--; n++;
         }
         // If the right boundary of the palindrome at the current position is greater than the right index, update the center index and the right index
         if ((i + lenPlandrm[i]) > right) {
            centerIndex = i; right = i + lenPlandrm[i];
         }
      }
      int len = 0; centerIndex = 0;
      // Find the maximum palindrome length and its center index
      for (int i = 1; i<s2.length; i++) {
         if (len < lenPlandrm[i]) {
            len = lenPlandrm[i]; centerIndex = i;
         }
      }
      // Construct the maximum palindrome
      char[] maxPalindrm = Arrays.copyOfRange(s2, centerIndex - len, centerIndex + len + 1);
      // Returning maximum palindrome
      return String.valueOf(removeBoundaries(maxPalindrm));
   }
   // Function to add boundaries to handle even length palindromes
   private static char[] addBoundaries(char[] cs) {
      if (cs == null || cs.length == 0)
         return "||".toCharArray();

      char[] cs2 = new char[cs.length * 2 + 1];
      for (int i = 0; i < (cs2.length - 1); i = i + 2) {
         cs2[i] = '|';
         cs2[i + 1] = cs[i / 2];
      }
      cs2[cs2.length - 1] = '|';
      return cs2;
   }
   // Function to remove the added boundaries from the result
   private static char[] removeBoundaries(char[] cs) {
      if (cs == null || cs.length < 3)
         return "".toCharArray();

      char[] cs2 = new char[(cs.length - 1) / 2];
      for (int i = 0; i < cs2.length; i++) {
         cs2[i] = cs[i * 2 + 1];
      }
      return cs2;
   }    
   public static void main(String[] args) {
      String orgnlString = "AAAABCAEAAABCBDDAAAAABC"; 
      System.out.println("Longest palindrome is: " + findLongestPalindrome(orgnlString)); 
   }
}

def add_boundaries(cs):
    if cs is None or len(cs) == 0:
        return ['|', '|']

    cs2 = ['|'] * (len(cs) * 2 + 1)
    for i in range(len(cs)):
        cs2[i * 2 + 1] = cs[i]
    return cs2

def remove_boundaries(cs):
    if cs is None or len(cs) < 3:
        return ""

    cs2 = [''] * ((len(cs) - 1) // 2)
    for i in range(len(cs2)):
        cs2[i] = cs[i * 2 + 1]
    return ''.join(cs2)

def find_longest_palindrome(orgnl_string):
    if orgnl_string is None or len(orgnl_string) == 0:
        return ""

    s2 = add_boundaries(list(orgnl_string))
    len_palandrm = [0] * len(s2)
    center_index = 0
    right = 0
    m = 0
    n = 0

    for i in range(1, len(s2)):
        if i > right:
            len_palandrm[i] = 0
            m = i - 1
            n = i + 1
        else:
            i2 = center_index * 2 - i
            if len_palandrm[i2] < (right - i - 1):
                len_palandrm[i] = len_palandrm[i2]
                m = -1
            else:
                len_palandrm[i] = right - i
                n = right + 1
                m = i * 2 - n

        while m >= 0 and n < len(s2) and s2[m] == s2[n]:
            len_palandrm[i] += 1
            m -= 1
            n += 1

        if (i + len_palandrm[i]) > right:
            center_index = i
            right = i + len_palandrm[i]

    length = 0
    center_index = 0
    for i in range(1, len(s2)):
        if length < len_palandrm[i]:
            length = len_palandrm[i]
            center_index = i

    max_palindrm = s2[center_index - length : center_index + length + 1]
    return remove_boundaries(max_palindrm)

orgnl_string = "AAAABCAEAAABCBDDAAAAABC"
print("Longest palindrome is:", find_longest_palindrome(orgnl_string))

输出

Longest palindrome is: AAAAA

打印页面