پرش به محتویات

الگوریتم ماناکر - یافتن تمام زیرپالیندروم‌ها در $O(N)$

صورت مسئله

رشته $s$ با طول $n$ داده شده است. تمام زوج‌های $(i, j)$ را به طوری پیدا کنید که زیررشته $s[i \dots j]$ یک پالیندروم باشد. رشته $t$ یک پالیندروم است هرگاه $t = t_{rev}$ باشد ($t_{rev}$ رشته معکوس $t$ است).

صورت مسئله دقیق‌تر

در بدترین حالت، یک رشته ممکن است تا $O(n^2)$ زیررشته پالیندرومی داشته باشد، و در نگاه اول به نظر می‌رسد که هیچ الگوریتم خطی برای این مسئله وجود ندارد.

اما اطلاعات مربوط به پالیندروم‌ها را می‌توان به صورت فشرده نگهداری کرد: برای هر موقعیت $i$، تعداد پالیندروم‌های ناتهی با مرکز این موقعیت را پیدا خواهیم کرد.

پالیندروم‌ها با یک مرکز مشترک، یک زنجیره پیوسته را تشکیل می‌دهند، یعنی اگر یک پالیندروم به طول $l$ با مرکز $i$ داشته باشیم، پالیندروم‌هایی با طول‌های $l-2$، $l-4$ و غیره نیز با مرکز $i$ خواهیم داشت. بنابراین، ما اطلاعات مربوط به تمام زیررشته‌های پالیندرومی را به این روش جمع‌آوری می‌کنیم.

پالیندروم‌های با طول فرد و زوج به صورت جداگانه با $d_{odd}[i]$ و $d_{even}[i]$ شمرده می‌شوند. برای پالیندروم‌های با طول زوج، فرض می‌کنیم مرکز آن‌ها در موقعیت $i$ است اگر دو کاراکتر مرکزی آن‌ها $s[i]$ و $s[i-1]$ باشند.

برای مثال، رشته $s = abababc$ سه پالیندروم با طول فرد با مرکز در موقعیت $s[3] = b$ دارد، یعنی $d_{odd}[3] = 3$:

$$a\ \overbrace{b\ a\ \underbrace{b}_{s_3}\ a\ b}^{\text{پالیندروم}} c$$

و رشته $s = cbaabd$ دو پالیندروم با طول زوج با مرکز در موقعیت $s[3] = a$ دارد، یعنی $d_{even}[3] = 2$:

$$c\ \overbrace{b\ a\ \underbrace{a}_{s_3}\ b}^{\text{پالیندروم}} d$$

این یک واقعیت شگفت‌انگیز است که الگوریتمی به اندازه کافی ساده وجود دارد که این "آرایه‌های پالیندرومی" $d_{odd}[]$ و $d_{even}[]$ را در زمان خطی محاسبه می‌کند. این الگوریتم در این مقاله توضیح داده شده است.

راه‌حل

به طور کلی، این مسئله راه‌حل‌های زیادی دارد: با درهم‌سازی رشته (String Hashing) می‌توان آن را در $O(n \cdot \log n)$ حل کرد، و با درخت‌های پسوندی (Suffix Trees) و LCA سریع، این مسئله در $O(n)$ قابل حل است.

اما روشی که در اینجا شرح داده شده است به مراتب ساده‌تر است و ثابت پنهان کمتری در پیچیدگی زمانی و حافظه دارد. این الگوریتم توسط Glenn K. Manacher در سال ۱۹۷۵ کشف شد.

یک روش مدرن دیگر برای حل این مسئله و به طور کلی کار با پالیندروم‌ها، از طریق چیزی است که درخت پالیندرومی یا eertree نامیده می‌شود.

الگوریتم بدیهی

برای جلوگیری از ابهامات در توضیحات بعدی، مشخص می‌کنیم که "الگوریتم بدیهی" چیست.

این الگوریتم به این صورت عمل می‌کند: برای هر موقعیت مرکزی $i$، سعی می‌کند پاسخ را یک به یک افزایش دهد تا زمانی که امکان دارد، و هر بار یک جفت کاراکتر متناظر را مقایسه می‌کند.

چنین الگوریتمی کند است و فقط می‌تواند پاسخ را در $O(n^2)$ محاسبه کند.

پیاده‌سازی الگوریتم بدیهی به این صورت است:

vector<int> manacher_odd_trivial(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    for(int i = 1; i <= n; i++) {
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

کاراکترهای پایانی $ و ^ برای این استفاده شده‌اند که نیازی به رسیدگی جداگانه به انتهای رشته نباشد.

الگوریتم ماناکر

الگوریتم را برای یافتن تمام زیرپالیندروم‌های با طول فرد، یعنی محاسبه $d_{odd}[]$، توضیح می‌دهیم.

برای محاسبه سریع، ما مرزهای انحصاری $(l, r)$ راست‌ترین (زیر)پالیندروم یافت‌شده را نگهداری می‌کنیم (یعنی راست‌ترین (زیر)پالیندروم فعلی $s[l+1] s[l+2] \dots s[r-1]$ است). در ابتدا $l = 0, r = 1$ قرار می‌دهیم که متناظر با رشته تهی است.

بنابراین، ما می‌خواهیم $d_{odd}[i]$ را برای $i$ بعدی محاسبه کنیم، و تمام مقادیر قبلی در $d_{odd}[]$ قبلاً محاسبه شده‌اند. به این صورت عمل می‌کنیم:

  • اگر $i$ خارج از زیرپالیندروم فعلی باشد، یعنی $i \geq r$، به سادگی الگوریتم بدیهی را اجرا می‌کنیم.

    بنابراین $d_{odd}[i]$ را به طور متوالی افزایش می‌دهیم و هر بار بررسی می‌کنیم که آیا زیررشته راست‌ترین فعلی $[i - d_{odd}[i]\dots i + d_{odd}[i]]$ یک پالیندروم است یا نه. وقتی اولین عدم تطابق را پیدا کنیم یا به مرزهای $s$ برسیم، متوقف می‌شویم. در این حالت، ما سرانجام $d_{odd}[i]$ را محاسبه کرده‌ایم. پس از این، نباید فراموش کنیم که $(l, r)$ را به‌روزرسانی کنیم. $r$ باید به گونه‌ای به‌روز شود که نمایانگر آخرین اندیس زیرپالیندروم راست‌ترین فعلی باشد.

  • حال حالتی را در نظر بگیرید که $i \le r$ باشد. سعی می‌کنیم از مقادیر قبلاً محاسبه شده در $d_{odd}[]$ اطلاعاتی استخراج کنیم. بنابراین، موقعیت "آینه‌ای" $i$ را در زیرپالیندروم $(l, r)$ پیدا می‌کنیم، یعنی موقعیت $j = l + (r - i)$ را به دست می‌آوریم، و مقدار $d_{odd}[j]$ را بررسی می‌کنیم. از آنجا که $j$ موقعیتی متقارن با $i$ نسبت به $(l+r)/2$ است، ما می‌توانیم تقریباً همیشه مقدار $d_{odd}[i] = d_{odd}[j]$ را اختصاص دهیم. تصویری از این موضوع (پالیندروم اطراف $j$ در واقع به پالیندروم اطراف $i$ "کپی" می‌شود):

    $$ \ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }_\text{پالیندروم}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{پالیندروم}\ \ldots\ s_{r-1}\ }^\text{پالیندروم}\ \ldots $$

    اما یک نکته ظریف وجود دارد که باید به درستی مدیریت شود: زمانی که پالیندروم "داخلی" به مرزهای پالیندروم "بیرونی" می‌رسد، یعنی $j - d_{odd}[j] \le l$ (یا به طور معادل، $i + d_{odd}[j] \ge r$). از آنجا که تقارن در خارج از پالیندروم "بیرونی" تضمین نشده است، صرفاً اختصاص دادن $d_{odd}[i] = d_{odd}[j]$ نادرست خواهد بود: ما داده‌های کافی برای این ادعا که پالیندروم در موقعیت $i$ همان طول را دارد، نداریم.

    در واقع، برای مدیریت صحیح چنین موقعیت‌هایی، باید طول پالیندروم خود را فعلاً محدود کنیم، یعنی $d_{odd}[i] = r - i$ را اختصاص دهیم. پس از این، الگوریتم بدیهی را اجرا می‌کنیم که سعی می‌کند $d_{odd}[i]$ را تا زمانی که امکان دارد افزایش دهد.

    تصویری از این حالت (پالیندروم با مرکز $j$ محدود شده است تا در پالیندروم "بیرونی" جای گیرد):

    $$ \ldots\ \overbrace{ \underbrace{ s_{l+1}\ \ldots\ s_j\ \ldots\ s_{j+(j-l)-1}\ }_\text{پالیندروم}\ \ldots\ \underbrace{ s_{i-(r-i)+1}\ \ldots\ s_i\ \ldots\ s_{r-1} }_\text{پالیندروم}\ }^\text{پالیندروم}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{تلاش برای گسترش به اینجا} $$

    همانطور که در تصویر نشان داده شده است، اگرچه پالیندروم با مرکز $j$ می‌توانست بزرگتر باشد و از پالیندروم "بیرونی" خارج شود، اما با مرکز $i$ ما فقط می‌توانیم از بخشی استفاده کنیم که کاملاً در پالیندروم "بیرونی" قرار می‌گیرد. اما پاسخ برای موقعیت $i$ ($d_{odd}[i]$) می‌تواند بسیار بزرگتر از این بخش باشد، بنابراین در ادامه الگوریتم بدیهی خود را اجرا می‌کنیم که سعی می‌کند آن را به خارج از پالیندروم "بیرونی" ما، یعنی به منطقه "تلاش برای گسترش به اینجا" گسترش دهد.

دوباره، نباید فراموش کنیم که مقادیر $(l, r)$ را پس از محاسبه هر $d_{odd}[i]$ به‌روزرسانی کنیم.

پیچیدگی الگوریتم ماناکر

در نگاه اول مشخص نیست که این الگوریتم دارای پیچیدگی زمانی خطی است، زیرا ما اغلب هنگام جستجوی پاسخ برای یک موقعیت خاص، الگوریتم بدیهی را اجرا می‌کنیم.

با این حال، یک تحلیل دقیق‌تر نشان می‌دهد که الگوریتم خطی است. در واقع، الگوریتم ساخت Z-function که شبیه به این الگوریتم به نظر می‌رسد، نیز در زمان خطی کار می‌کند.

می‌توانیم متوجه شویم که هر تکرار الگوریتم بدیهی، $r$ را یک واحد افزایش می‌دهد. همچنین $r$ در طول الگوریتم نمی‌تواند کاهش یابد. بنابراین، الگوریتم بدیهی در مجموع $O(n)$ تکرار خواهد داشت.

سایر بخش‌های الگوریتم ماناکر به وضوح در زمان خطی کار می‌کنند. بنابراین، ما به پیچیدگی زمانی $O(n)$ می‌رسیم.

پیاده‌سازی الگوریتم ماناکر

برای محاسبه $d_{odd}[]$، کد زیر را به دست می‌آوریم. نکات قابل توجه:

  • $i$ اندیس حرف مرکزی پالیندروم فعلی است.
  • اگر $i$ از $r$ بزرگتر شود، $d_{odd}[i]$ با مقدار اولیه ۰ مقداردهی می‌شود.
  • اگر $i$ از $r$ بزرگتر نباشد، $d_{odd}[i]$ یا با مقدار $d_{odd}[j]$ مقداردهی اولیه می‌شود که $j$ موقعیت آینه‌ای $i$ در $(l,r)$ است، یا $d_{odd}[i]$ به اندازه پالیندروم "بیرونی" محدود می‌شود.
  • حلقه while الگوریتم بدیهی را نشان می‌دهد. ما آن را صرف‌نظر از مقداری که در ابتدا به p[i] اختصاص داده‌ایم، اجرا می‌کنیم.
  • اگر طول پالیندروم با مرکز $i$ برابر $x$ باشد، آنگاه $d_{odd}[i]$ مقدار $\frac{x+1}{2}$ را ذخیره می‌کند.
vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    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);
}

کار با زوجیت‌ها

اگرچه می‌توان الگوریتم ماناکر را برای طول‌های فرد و زوج به طور جداگانه پیاده‌سازی کرد، پیاده‌سازی نسخه برای طول‌های زوج اغلب دشوارتر تلقی می‌شود، زیرا کمتر طبیعی است و به راحتی منجر به خطاهای یکی کمتر/بیشتر (off-by-one) می‌شود.

برای کاهش این مشکل، می‌توان کل مسئله را به حالتی کاهش داد که فقط با پالیندروم‌های با طول فرد سروکار داریم. برای این کار، می‌توانیم یک کاراکتر # اضافی بین هر حرف در رشته و همچنین در ابتدا و انتهای رشته قرار دهیم:

$$abcbcba \to \#a\#b\#c\#b\#c\#b\#a\#$$

هر پالیندروم در رشته اصلی (چه با طول فرد و چه زوج) به یک پالیندروم با طول فرد در رشته جدید تبدیل می‌شود. پالیندروم‌های با طول فرد در رشته اصلی، در رشته جدید نیز حول همان حروف مرکزی قرار دارند. پالیندروم‌های با طول زوج در رشته اصلی، در رشته جدید حول کاراکترهای # قرار می‌گیرند.

این کاهش به صورت زیر پیاده‌سازی می‌شود:

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);
}

برای سادگی، تقسیم آرایه به $d_{odd}$ و $d_{even}$ و همچنین محاسبه صریح آنها حذف شده است. آرایه نتیجه حاوی تمام اطلاعات لازم برای استخراج پالیندروم‌های هر دو نوع است.

مسائل