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
列印頁面
上一頁
下一頁
廣告