Manacher’s Algorithm

Manacher’s Algorithm เป็น algorithm ที่หา longest palindromic substring ที่มีจุดศูนย์กลางที่ทุกตำแหน่ง ใน time complexity $O(n)$

ปัญหา

หา array $d$ โดยที่:

• $d_1[i]$ = จำนวน palindrome ความยาวคี่ที่มี center ที่ตำแหน่ง $i$ (นับ radius รวม center)
• $d_2[i]$ = จำนวน palindrome ความยาวคู่ที่มี center ระหว่างตำแหน่ง $i-1$ และ $i$

แนวคิด

คล้ายกับ Z-function ใช้ข้อมูลที่คำนวณไว้แล้วเพื่อเร่งการคำนวณตำแหน่งถัดไป

ใช้ rightmost palindrome ที่พบแล้ว (center $c$, right boundary $r$)

Implementation

Odd-length Palindromes

vector<int> manacherOdd(const string& s) {
    int n = s.size();
    vector<int> d(n, 1);  // d[i] = radius of palindrome centered at i
    
    int l = 0, r = -1;  // current rightmost palindrome [l, r]
    
    for (int i = 0; i < n; i++) {
        int k = 1;
        if (i <= r) {
            // Mirror position: i' = l + (r - i)
            k = min(d[l + r - i], r - i + 1);
        }
        
        // Expand palindrome
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        
        d[i] = k;
        
        // Update rightmost palindrome
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }
    
    return d;
}

Even-length Palindromes

vector<int> manacherEven(const string& s) {
    int n = s.size();
    vector<int> d(n, 0);  // d[i] = radius of palindrome centered between i-1 and i
    
    int l = 0, r = -1;
    
    for (int i = 0; i < n; i++) {
        int k = 0;
        if (i <= r) {
            k = min(d[l + r - i + 1], r - i + 1);
        }
        
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        
        d[i] = k;
        
        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }
    
    return d;
}

Combined Version (ใช้ separator)

แปลง string ด้วย separator เพื่อจัดการทั้ง odd และ even:

string transform(const string& s) {
    string t = "^";  // start sentinel
    for (char c : s) {
        t += "#";
        t += c;
    }
    t += "#$";  // end sentinel
    return t;
}

vector<int> manacher(const string& s) {
    string t = transform(s);
    int n = t.size();
    vector<int> p(n, 0);
    
    int c = 0, r = 0;  // center and right boundary
    
    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * c - i;
        
        if (i < r) {
            p[i] = min(r - i, p[mirror]);
        }
        
        // Expand
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
            p[i]++;
        }
        
        // Update center
        if (i + p[i] > r) {
            c = i;
            r = i + p[i];
        }
    }
    
    return p;
}

ตัวอย่าง

String: "abacaba"

Transformed: "^#a#b#a#c#a#b#a#$"

Index:  0 1 2 3 4 5 6 7 8 9 ...
Char:   ^ # a # b # a # c # ...
p[i]:   0 0 1 0 3 0 1 0 7 0 ...

$p[8] = 7$ หมายถึง palindrome "abacaba" มี radius 7 (ใน transformed string)

ประยุกต์ใช้งาน

1. Longest Palindromic Substring

string longestPalindrome(const string& s) {
    vector<int> p = manacher(s);
    
    int maxLen = 0, center = 0;
    for (int i = 1; i < p.size() - 1; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            center = i;
        }
    }
    
    // Convert back to original string
    int start = (center - maxLen) / 2;
    return s.substr(start, maxLen);
}

2. นับจำนวน Palindromic Substrings

long long countPalindromes(const string& s) {
    vector<int> d1 = manacherOdd(s);
    vector<int> d2 = manacherEven(s);
    
    long long count = 0;
    
    // Odd-length palindromes
    for (int x : d1) count += x;
    
    // Even-length palindromes
    for (int x : d2) count += x;
    
    return count;
}

3. Check if Substring is Palindrome

struct PalindromeChecker {
    vector<int> d1, d2;
    
    PalindromeChecker(const string& s) {
        d1 = manacherOdd(s);
        d2 = manacherEven(s);
    }
    
    // Check if s[l..r] is palindrome (0-indexed)
    bool isPalindrome(int l, int r) {
        int len = r - l + 1;
        int mid = (l + r) / 2;
        
        if (len % 2 == 1) {
            // Odd length: center at mid
            return d1[mid] >= (len + 1) / 2;
        } else {
            // Even length: center between mid and mid+1
            return d2[mid + 1] >= len / 2;
        }
    }
};

Complexity

Operation	Time	Space
Build arrays	$O(n)$	$O(n)$
Query substring	$O(1)$	-

Tips

1. Transformed string ทำให้จัดการ odd/even ง่ายขึ้น
2. Sentinel characters ป้องกัน boundary check
3. Mirror property คือหัวใจของ algorithm - ใช้ palindrome ที่รู้แล้วช่วยคำนวณ
4. ความยาวจริง = p[i] ใน transformed string (เมื่อใช้ separator)