อัลกอริทึม Manacher สำหรับหา Palindrome ยาวที่สุด

บทนำ

อัลกอริทึม Manacher ใช้หา Substring แบบ Palindrome (อ่านจากหน้าหลังได้เหมือนกัน) ที่ยาวที่สุดในสตริง โดยเลือกตัวอักษรแต่ละตัวเป็นศูนย์กลาง แล้วขยายไปซ้าย-ขวา มีอาร์เรย์เก็บข้อมูลความยาว Palindrome ที่ศูนย์กลางแต่ละตำแหน่ง

ความซับซ้อนของเวลา (Time Complexity)

O(n) โดย n คือความยาวสตริง

อินพุตและเอาต์พุต

Input: String: "levelup"
Output: Longest palindrome is: level

อัลกอริทึม

longestPalindrome(text)

Input: ข้อความที่ต้องการหา palindrome ยาวที่สุด
Output: palindrome ยาวที่สุดในข้อความ

Begin
    n := ขนาด text
    if n = 0 then return สตริงว่าง
    n := 2n + 1
    กำหนดอาร์เรย์ longPal ขนาด n
    longPal[0] := 0, longPal[1] := 1
    centerIndex := 1, rightIndex := 2
    right := 0
    maxPalLength := 0, maxCenterIndex := 0
    start := -1, end := -1, diff := -1
    
    for right := 2 ถึง n-1 do
        left := 2*centerIndex - right
        longPal[right] := 0
        diff := rightIndex - right
        if diff > 0 then
            longPal[right] := min(longPal[left], diff)
        while (right + longPal[right]) < n AND (right - longPal[right]) > 0 AND
              ((right + longPal[right]+1) mod 2 = 0 OR
               text[(right + longPal[right] + 1)/2] = text[(right - longPal[right]-1)/2]) do
            เพิ่ม longPal[right] 1
        done
        if longPal[right] > maxPalLength then
            maxPalLength := longPal[right]
            maxCenterIndex := right
        if (right + longPal[right]) > rightIndex then
            centerIndex := right
            rightIndex := right + longPal[right]
    done
    
    start := (maxCenterIndex - maxPalLength)/2
    end := start + maxPalLength - 1
    palindrome = substring ของ text[start..end]
    return palindrome
End

ตัวอย่างโค้ด (C++)

#include<iostream>
using namespace std;

int min(int a, int b) { return (a 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;
}

ผลลัพธ์

Enter String: levelup
Longest palindrome is: level