Palindromic Substring খোঁজা — Part 2: Manacher's Algorithm O(n)

এই article পড়ার আগে Part 1: O(n³) ও O(n²) সমাধান পড়ে নাও — সেখানে palindrome কী, brute force, এবং center expansion বিস্তারিত ব্যাখ্যা করা আছে।

Part 1 থেকে যেখানে ছিলাম

Part 1 এ আমরা দেখেছি:

• O(n³) Brute Force: সব substring enumerate করে palindrome check — অনেক ধীর
• O(n²) Center Expansion: প্রতিটা position কে center ধরে দুইদিকে expand — অনেক ভালো, কিন্তু এখনো যথেষ্ট না

Center expansion এ মূল সমস্যা: আমরা আগে যা জেনেছি তা ভুলে যাই।

ধরো "abacaba" — center 3 (c) থেকে expand করে আমরা জানি পুরো string টাই palindrome। এখন center 5 (a) তে গেলে, আবার শুরু থেকে expand করি! কিন্তু center 5 তো center 3 এর palindrome এর ভেতরেই আছে — এই তথ্য কি কাজে লাগানো যায় না?

Manacher's Algorithm ঠিক এটাই করে।

মূল কৌশল — ৩টা জিনিস track করা

Algorithm চলাকালীন আমরা ৩টা জিনিস মনে রাখি:

1. C (Center): এখন পর্যন্ত যে palindrome সবচেয়ে ডানে পৌঁছেছে, তার center
2. R (Right boundary): সেই palindrome এর ডান প্রান্ত (exclusive — অর্থাৎ palindrome R-1 পর্যন্ত)
3. p[] array: প্রতিটি position এর palindrome radius (যা আমরা বের করছি)

s = ... [=====C=====R) ...
         ← palindrome →

R এর মানে: index 0 থেকে R-1 পর্যন্ত কোথাও না কোথাও একটা palindrome এর অংশ — এই range এর ভেতরে নতুন position process করতে গেলে আমরা shortcut নিতে পারি।

এখন position i process করব — দুইটা case

Case 1: i >= R (boundary এর বাইরে)

s = ... [=====C=====R)  ...  i  ...
                              ↑
                    আমরা এখন এখানে, R এর বাইরে

আমাদের কাছে i সম্পর্কে কোনো আগের তথ্য নেই। তাই উপায় নেই — trivial ভাবে expand করতে হবে: i থেকে দুইদিকে character মেলাও, যতক্ষণ মেলে ততক্ষণ p[i]++ করো।

Expand শেষ হলে, যদি i + p[i] > R হয়, তাহলে C আর R update করো — কারণ এখন এই নতুন palindrome সবচেয়ে ডানে গেছে।

Case 2: i < R (boundary এর ভেতরে) — এখানেই যাদু!

s = ... [  j  ===C===  i  )R ...
         ↑              ↑
       mirror        current

i যেহেতু C-centered palindrome এর ভেতরে, তাই C এর বাম দিকে i এর একটা আয়না প্রতিবিম্ব (mirror) আছে:

j = 2 * C - i

কেন? C হলো palindrome এর center। Palindrome মানেই বাম আর ডান symmetric। তাই C থেকে i যতটা ডানে, j ততটাই বামে।

এখন j এর palindrome radius p[j] আমরা আগেই বের করেছি। Mirror property অনুযায়ী: C-centered palindrome এর ভেতরে, i এর চারপাশের characters আর j এর চারপাশের characters হুবহু একই (কারণ palindrome symmetric)!

তাহলে p[i] তে কি সরাসরি p[j] বসিয়ে দেওয়া যায়? নির্ভর করে! তিনটা sub-case:

Sub-case 2a: j এর palindrome পুরোটা (l, R) এর ভেতরে

s = ... [ (--j--)  C  (--i--) )R ...

j এর palindrome boundary ছুঁচ্ছে না — তাহলে symmetry guarantee করে i এর palindrome ও exactly same।

→ p[i] = p[j] — কোনো expansion লাগবে না! 🎉

Sub-case 2b: j এর palindrome বাম boundary (l) ছুঁয়ে গেছে বা বাইরে গেছে

s = (--j===[==  C  ==)i===???)R ...
        ↑ l                    ↑
  j এর palindrome বাইরে চলে গেছে

j এর palindrome l boundary পার করে গেছে। Symmetry শুধু (l, R) range এর ভেতরে guarantee করে — বাইরে কি হবে আমরা জানি না।

→ p[i] = R - i (যতটুকু guarantee আছে ততটুকু নাও), তারপর R এর পর থেকে trivial expand করো — হয়তো আরো বাড়বে, হয়তো না।

Sub-case 2c: j এর palindrome ঠিক boundary তে শেষ

এটা 2b এর মতোই — p[i] = R - i দিয়ে শুরু করে expand করো। কারণ boundary এর ঠিক বাইরে কী আছে, symmetry সেটা বলতে পারে না।

সবকিছু একসাথে — Pseudocode

for each position i:
    if i < R:
        j = 2 * C - i          // mirror position
        p[i] = min(p[j], R - i) // যতটুকু guarantee, ততটুকু নাও

    // এরপর expand (trivially)
    while s[i - p[i] - 1] == s[i + p[i] + 1]:
        p[i]++

    // boundary update
    if i + p[i] > R:
        C = i
        R = i + p[i]

লক্ষ্য করো: min(p[j], R - i) — এক লাইনেই তিনটা sub-case handle হয়ে যাচ্ছে!

• p[j] < R - i → sub-case 2a (mirror copy, while loop চলবে না)
• p[j] >= R - i → sub-case 2b/2c (R-i নিয়ে expand শুরু)

কেন O(n)? — সময় জটিলতার প্রমাণ

এটা বোঝা গুরুত্বপূর্ণ। দেখে মনে হতে পারে while loop থাকায় O(n²) হবে — কিন্তু না!

Key observation: while loop এর প্রতিটা iteration এ R অন্তত ১ বাড়ে।

• R শুরু হয় 0 থেকে
• R সর্বোচ্চ n পর্যন্ত যেতে পারে
• R কখনো কমে না (শুধু বাড়ে বা same থাকে)

তাহলে পুরো algorithm জুড়ে while loop মোট সর্বোচ্চ n বার চলতে পারে — প্রতি position এ গড়ে O(1)!

• বাকি সব কাজ (mirror copy, boundary check) = O(1) per position
• n টা position × O(1) = O(n) মোট!

সব expansion মিলিয়ে R সর্বোচ্চ n বার বাড়ে → O(n)!

বিস্তারিত Walkthrough — ধাপে ধাপে

ধরো s = "abacaba"। transformed string হবে "#a#b#a#c#a#b#a#"।

Algorithm শুরু হয়: C = 0, R = 0, p[] = [0, 0, 0, ...]

i = 1 ('a'): R এর বাইরে, trivial expand → p[1] = 1 (palindrome: "a")। Update: C=1, R=2।

i = 3 ('b'): R এর বাইরে, expand → p[3] = 1 (palindrome: "b")। Update: C=3, R=4।

i = 5 ('a'): R এর বাইরে, expand → p[5] = 3 (palindrome: "#a#b#a#" = "aba")। Update: C=5, R=8।

i = 7 ('c'): i < R (7 < 8)! Mirror = 2×5 - 7 = 3, p[3] = 1। কিন্তু i + p[mirror] = 7+1 = 8 = R, boundary ছুঁয়ে গেছে! তাই p[7] = 1 থেকে শুরু করে expand → p[7] = 7 (palindrome: "abacaba")! Update: C=7, R=14।

i = 9 ('a'): i < R, Mirror = 5, p[5] = 3। i + p[5] = 12 < R=14, পুরোটা ভেতরে → p[9] = p[5] = 3। কোনো expansion লাগলো না! — এটাই Manacher এর ক্ষমতা!

Interactive Simulation

নিচের simulation এ নিজে দেখো কিভাবে algorithm কাজ করে। Input বদলাও, step by step দেখো:

Implementation — Odd-length

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";   // sentinel characters
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = min(r - i, p[l + (r - i)]);
        while (s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if (i + p[i] > r) {
            l = i - p[i];
            r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

Sentinel characters: শুরুতে $ আর শেষে ^ যোগ করি যেন boundary check এর দরকার না হয়। এই দুটো character string এ থাকবে না, তাই while loop নিজে থেকেই থেমে যাবে।

Even-length palindromes কিভাবে handle করব?

আলাদা আলাদা even-length এর জন্য code লেখার বদলে একটা চালাকি আছে — string এ প্রতিটি character এর মাঝে # বসিয়ে দাও:

"abc" → "#a#b#c#"

এখন even-length palindromes গুলো # এর উপর centered odd-length palindrome হয়ে যাবে!

vector<int> manacher(string s) {
    string t;
    for (auto c : s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

Transformed array থেকে মূল তথ্য বের করা

transformed string এর result d[] থেকে:

• d[2*i] → even-length palindromes: d_even[i] = d[2*i] / 2
• d[2*i + 1] → odd-length palindromes: d_odd[i] = (d[2*i + 1] + 1) / 2

সময় জটিলতা (Time Complexity)

O(n) — কারণ r শুধু বাড়ে, কমে না। মোট expansion across all positions = O(n)।

অনুশীলন সমস্যা (Practice Problems)

• Enumerate Palindromes — Library Checker
• Longest Palindrome — CSES
• Longest Palindrome Substring — LeetCode 5
• Palindromic Substrings — LeetCode 647
• Palindrome Degree — Codeforces 7D
• Palindrome Pairs — Codeforces 17E
• EPALIN — SPOJ

সারমর্ম

সম্পূর্ণ সিরিজ