Thuật toán Manacher tìm Palindrome dài nhất

Giới thiệu

Để tìm chuỗi con đối xứng (palindrome) dài nhất, Manacher's Algorithm là lựa chọn tối ưu. Với mỗi ký tự làm trung tâm, dùng hai con trỏ trái/phải mở rộng. Mảng phụ lưu thông tin độ dài palindrome tại mỗi vị trí. Sau khi duyệt hết chuỗi, tìm giá trị lớn nhất trong mảng.

Độ phức tạp: O(n).

Đầu vào và Đầu ra

Đầu vào: Chuỗi: "levelup"
Đầu ra: Longest palindrome is: level

Thuật toán

longestPalindrome(text)

Đầu vào: Chuỗi cần tìm palindrome dài nhất

Đầu ra: Chuỗi palindrome dài nhất

Begin
  n := kích thước text
  nếu n = 0 thì trả về chuỗi rỗng
  n := 2n + 1
  định nghĩa mảng longPal kích thước n
  longPal[0] := 0, longPal[1] := 1
  centerIndex := 1, rightIndex := 2, right := 0
  maxPalLength := 0, maxCenterIndex := 0
  start := -1, end := -1, diff := -1
  với right := 2 đến n-1 làm:
    left := 2*centerIndex - right
    longPal[right] := 0
    diff := rightIndex - right
    nếu diff > 0 thì longPal[right] := min(longPal[left], diff)
    trong khi (right + longPal[right]) < n VÀ (right - longPal[right]) > 0 VÀ
      ((right + longPal[right] + 1) mod 2 = 0 HOẶC
      text[(right + longPal[right] + 1)/2] = text[(right - longPal[right] - 1)/2]) làm
      tăng longPal[right] 1
    done
    nếu longPal[right] > maxPalLength thì
      maxPalLength := longPal[right]
      maxCenterIndex := right
    nếu (right + longPal[right]) > rightIndex thì
      centerIndex := right
      rightIndex := right + longPal[right]
  done
  start := (maxCenterIndex - maxPalLength)/2
  end := start + maxPalLength - 1
  palindrome = chuỗi con text[start..end]
  trả về palindrome
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int min(int a, int b) { return (a < b) ? a : b; }

string longestPalindrome(string mainString) {
  int n = mainString.size();
  if(n == 0) return "";
  n = 2 * n + 1;
  int longPal[n];
  longPal[0] = 0; longPal[1] = 1;
  int centerIndex = 1, rightIndex = 2;
  int right = 0, left;
  int maxPalLength = 0, maxCenterIndex = 0;
  int start = -1, end = -1, diff = -1;
  for (right = 2; right < n; right++) {
    left = 2 * centerIndex - right;
    longPal[right] = 0;
    diff = rightIndex - right;
    if(diff > 0) longPal[right] = min(longPal[left], diff);
    while ( ((right + longPal[right]) < n && (right - longPal[right]) > 0) &&
      ( ((right + longPal[right] + 1) % 2 == 0) ||
      (mainString[(right + longPal[right] + 1)/2] == mainString[(right - longPal[right] - 1)/2] ))) {
      longPal[right]++;
    }
    if(longPal[right] > maxPalLength) {
      maxPalLength = longPal[right];
      maxCenterIndex = right;
    }
    if (right + longPal[right] > rightIndex) {
      centerIndex = right;
      rightIndex = right + longPal[right];
    }
  }
  start = (maxCenterIndex - maxPalLength) / 2;
  end = start + maxPalLength - 1;
  string palindrome;
  for(int i = start; i <= end; i++) palindrome += mainString[i];
  return palindrome;
}

int main() {
  string mainString, palindrome;
  cout << "Enter String:";
  cin >> mainString;
  palindrome = longestPalindrome(mainString);
  cout << "Longest palindrome is: " << palindrome << endl;
}

Kết quả đầu ra

Enter String: levelup
Longest palindrome is: level