Манакерийн алгоритм - бүх дэд палиндромыг $O(N)$-д олох¶

Бодлогын тавил¶

$n$ урттай $s$ тэмдэгт мөр өгөгдсөн. $s[i\dots j]$ дэд мөр палиндром байх бүх $(i, j)$ хосыг ол. $t$ тэмдэгт мөр $t = t_{rev}$ үед палиндром байна ($t_{rev}$ нь $t$-ийн урвуу тэмдэгт мөр).

Илүү нарийвчилсан тавил¶

Хамгийн муу тохиолдолд тэмдэгт мөр $O(n^2)$ хүртэл палиндром дэд мөртэй байж болох бөгөөд эхлээд харахад энэ бодлогод шугаман алгоритм байхгүй мэт санагдана.

Гэвч палиндромуудын тухай мэдээллийг авсаархан аргаар хадгалж болно: байрлал $i$ бүрийн хувьд бид энэ байрлалд төвтэй хоосон биш палиндромуудын тоог олно.

Нийтлэг төвтэй палиндромууд дараалсан гинж үүсгэнэ, өөрөөр хэлбэл хэрэв бидэнд $i$-д төвтэй $l$ урттай палиндром байвал мөн $i$-д төвтэй $l-2$, $l-4$ гэх мэт урттай палиндромууд бас байна. Тиймээс бид бүх палиндром дэд мөрийн тухай мэдээллийг ийм байдлаар цуглуулна.

Сондгой ба тэгш урттай палиндромуудыг $d_{odd}[i]$ ба $d_{even}[i]$ гэж тусад нь тооцно. Тэгш урттай палиндромуудын хувьд тэдгээрийн хоёр төв тэмдэгт нь $s[i]$ ба $s[i-1]$ бол тэдгээрийг $i$ байрлалд төвтэй гэж үзнэ.

Жишээ нь $s = abababc$ тэмдэгт мөр $s[3] = b$ байрлалд төвтэй, сондгой урттай гурван палиндромтой, өөрөөр хэлбэл $d_{odd}[3] = 3$:

$$a\ \overbrace{b\ a\ \underbrace{b}_{s_3}\ a\ b}^{d_{odd}[3]=3} c$$

Мөн $s = cbaabd$ тэмдэгт мөр $s[3] = a$ байрлалд төвтэй, тэгш урттай хоёр палиндромтой, өөрөөр хэлбэл $d_{even}[3] = 2$:

$$c\ \overbrace{b\ a\ \underbrace{a}_{s_3}\ b}^{d_{even}[3]=2} d$$

Эдгээр "палиндром чанарын массив" $d_{odd}[]$ ба $d_{even}[]$-г шугаман хугацаанд тооцоолдог, хангалттай энгийн алгоритм байдаг нь гайхалтай баримт юм. Уг алгоритмыг энэ өгүүлэлд тайлбарлав.

Шийдэл¶

Ерөнхийдөө энэ бодлого олон шийдэлтэй: Тэмдэгт мөрийн хэшлэлт-ээр үүнийг $O(n\cdot \log n)$-д бодож болох ба Дагаврын мод ба хурдан LCA-ээр энэ бодлогыг $O(n)$-д бодож болно.

Гэвч энд тайлбарласан арга нь хангалттай энгийн бөгөөд хугацаа, санах ойн complexity-д бага нуугдмал тогтмолтой. Энэ алгоритмыг Glenn K. Manacher 1975 онд нээсэн.

Энэ бодлогыг бодох, ерөнхийдөө палиндромтой ажиллах өөр нэг орчин үеийн арга бол палиндром мод буюу 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$ гэж тохируулах ба энэ нь хоосон тэмдэгт мөрд харгалзана.

Тэгэхээр бид дараагийн $i$-ийн хувьд $d_{odd}[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}[]$ дэх аль хэдийн тооцоолсон утгуудаас зарим мэдээлэл гаргаж авахыг оролдоно. Тиймээс $(l, r)$ дэд палиндром дахь $i$-ийн "толин" байрлалыг олъё, өөрөөр хэлбэл бид $j = l + (r - i)$ байрлалыг авч, $d_{odd}[j]$-ийн утгыг шалгана. $j$ нь $(l+r)/2$-ын хувьд $i$-тэй тэгш хэмтэй байрлал тул бид бараг үргэлж $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{palindrome}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ s_{r-1}\ }^\text{palindrome}\ \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{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)+1}\ \ldots\ s_i\ \ldots\ s_{r-1} }_\text{palindrome}\ }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here} $$

$j$ төвтэй палиндром илүү том байж, "гадаад" палиндромын гадна гарч болохыг дүрслэлээс харуулсан ч $i$-г төв болгосон үед бид зөвхөн "гадаад" палиндромд бүхэлдээ багтах хэсгийг л ашиглаж болно. Гэвч $i$ байрлалын хариу ($d_{odd}[i]$) энэ хэсгээс хамаагүй том байж болох тул дараа нь бид түүнийг "гадаад" палиндромынхоо гадна буюу "try moving here" муж руу өсгөхийг оролдох тривиаль алгоритмаа ажиллуулна.

Дахин хэлэхэд бид $d_{odd}[i]$ бүрийг тооцоолсны дараа $(l, r)$ утгуудыг шинэчлэхээ мартаж болохгүй.

Манакерийн алгоритмын complexity¶

Эхлээд харахад энэ алгоритм шугаман time complexity-тэй нь илэрхий биш, учир нь бид тодорхой байрлалын хариуг хайх явцад гэнэн алгоритмыг олонтаа ажиллуулдаг.

Гэвч илүү нарийн шинжилгээ алгоритм шугаман болохыг харуулна. Үнэндээ энэ алгоритмтай төстэй харагддаг Z-функц байгуулах алгоритм мөн шугаман хугацаанд ажилладаг.

Тривиаль алгоритмын давталт бүр $r$-г нэгээр нэмэгдүүлдгийг бид анзаарч болно. Мөн алгоритмын явцад $r$ багасаж чадахгүй. Тиймээс тривиаль алгоритм нийтдээ $O(n)$ давталт хийнэ.

Манакерийн алгоритмын бусад хэсэг илэрхий шугаман хугацаанд ажиллана. Ингэснээр бид $O(n)$ time complexity авна.

Implementation of Manacher's algorithm¶

For calculating $d_{odd}[]$, we get the following code. Things to note:

$i$ is the index of the center letter of the current palindrome.
If $i$ exceeds $r$, $d_{odd}[i]$ is initialized to 0.
If $i$ does not exceed $r$, $d_{odd}[i]$ is either initialized to the $d_{odd}[j]$, where $j$ is the mirror position of $i$ in $(l,r)$, or $d_{odd}[i]$ is restricted to the size of the "outer" palindrome.
The while loop denotes the trivial algorithm. We launch it irrespective of the value of $k$.
If the size of palindrome centered at $i$ is $x$, then $d_{odd}[i]$ stores $\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++) {
        if(i <= r) {
            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);
}

Тэгш сондгой байдалтай ажиллах¶

Манакерийн алгоритмыг сондгой ба тэгш урттай хувилбаруудад тусад нь хэрэгжүүлэх боломжтой ч тэгш урттай хувилбарын хэрэгжүүлэлтийг ихэвчлэн илүү хэцүү гэж үздэг, учир нь энэ нь бага байгалийн бөгөөд нэгээр зөрөх алдаанд амархан хүргэдэг.

Үүнийг зөөлрүүлэхийн тулд бүхэл бодлогыг зөвхөн сондгой урттай палиндромтой ажиллах тохиолдол болгон хураах боломжтой. Үүний тулд бид тэмдэгт мөрийн үсэг бүрийн хооронд, мөн тэмдэгт мөрийн эхэн ба төгсгөлд нэмэлт # тэмдэгт тавьж болно:

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

$$d = [1,2,1,2,1,4,1,8,1,4,1,2,1,2,1].$$

Таны харж байгаагаар $d[2i]=2 d_{even}[i]+1$ ба $d[2i+1]=2 d_{odd}[i]$ байна, энд $d$ нь #-ээр холбосон тэмдэгт мөр дэх сондгой урттай палиндромуудын Манакерийн массивыг тэмдэглэх ба $d_{odd}$, $d_{even}$ нь анхны тэмдэгт мөрд дээр тодорхойлсон массивуудад харгалзана.

Үнэхээр # тэмдэгтүүд нь анхны тэмдэгт мөрийн тэмдэгтүүдэд төвтэй хэвээр байгаа сондгой урттай палиндромуудад нөлөөлөхгүй, харин одоо анхны тэмдэгт мөрийн тэгш урттай палиндромууд нь # тэмдэгтүүдэд төвтэй, шинэ тэмдэгт мөрийн сондгой урттай палиндромууд болно.

$d[2i]$ ба $d[2i+1]$ нь үндсэндээ $i$-д төвтэй хамгийн том сондгой ба тэгш урттай палиндромуудын урт дээр $1$ нэмсэнтэй харгалзан тэнцүү болохыг анзаар.

Хураалтыг дараах байдлаар хэрэгжүүлнэ:

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}$ болгон хуваах, мөн тэдгээрийг ил тооцоолохыг орхигдуулсан.