Manaker algoritmi
Manacher algoritmi berilgan satrda subpalindromlarni chiziqli vaqt ichida topish uchun ishlatiladi. Yanada rasmiyroq masala qo‘yilishi quyidagicha ko‘rinadi: Uzunligi bo‘lgan satri berilgan. ostsatri palindrom bo‘ladigan barcha juftliklarni toping. satri palindrom deyiladi, agar ( - uchun teskari satr).
To‘g‘ridan-to‘g‘ri yechim berilgan satrning har bir belgisi bo‘yicha iteratsiya qilish va uni palindrom markazi sifatida ko‘rib chiqish bo‘lishi mumkin, ya’ni qo‘shni belgilarni ko‘rib chiqish va har safar mos belgilar juftini solishtirib, imkon qadar pozitsiyalarni kengaytirish. To‘lib ketish va chap hamda o‘ng chegaralardan chiqib ketishni oldini olish uchun, biz bu chegaralarning terminal belgilanishlarini qo‘shishimiz mumkin.
Trivial algoritmning realizatsiyasi quyidagicha ko‘rinadi:
Terminal belgilar $ va ^ satr uchlarini alohida qayta ishlamaslik uchun ishlatilgan.
markazli toq uzunlikdagi palindromlarni bildirsin. - topilgan eng o‘ngdagi (sub)palindromning chegaralari bo‘lsin (ya’ni joriy eng o‘ngdagi (sub)palindrom - ). Dastlab , bu bo‘sh satrga teng.
Keyin biz ni hisoblamoqchimiz, shuning uchun:
Bunday vaziyatlar bilan to‘g‘ri ishlash uchun hozircha palindrom uzunligini cheklashimiz kerak, ya’ni , . Shundan so‘ng biz yuqorida tasvirlangan oddiy yondashuvni ishga tushiramiz, u imkon qadar ni oshirishga harakat qiladi.
Bu holatning illyustratsiyasi ( markazli palindrom "tashqi" palindromga sig‘ishi uchun cheklanadi):
. Rasmda ko‘rsatilishicha, markazli palindrom kattaroq bo‘lishi va "tashqi" palindromdan tashqariga chiqishi mumkin bo‘lsa-da, lekin markaz sifatida bilan biz faqat "tashqi" palindrom ichiga to‘liq sig‘adigan qismini ishlata olamiz. Ammo pozitsiyasi uchun javob ( ) bu qismdan ancha katta bo‘lishi mumkin, shuning uchun keyin biz trivial algoritmimizni ishga tushiramiz, u uni "tashqi" palindromdan tashqariga, ya’ni "bu yerga siljitishga urinib ko‘ring" sohasiga o‘stirishga harakat qiladi. Eslatib o‘tamiz, to‘g‘ri ishlash uchun har bir hisoblangandan so‘ng qiymatlarini yangilashimiz kerak.
Toq uzunlikdagi Manacher algoritmi uchun realizatsiya:
Garchi biz yuqorida tasvirlangan yondashuvdan foydalanib, uni juft uzunlikdagi satr markazi sifatida ikki belgini ko‘rib chiqish uchun modifikatsiya qila olsak-da, butun muammoni faqat toq uzunlikdagi palindromlar bilan ishlaydigan holatga keltirish mumkin. Buning uchun satrdagi har bir harf orasiga, shuningdek satr boshiga va oxiriga qo‘shimcha belgisini qo‘yishimiz mumkin. Bu mavjud palindromlarning xossalarini saqlab qoladi va satrni toq qiladi:
.
Bu yerda va , bu yerda -qo‘shni satrda toq uzunlikdagi palindromlar uchun Manacher massivi, va esa yuqorida asl satrda aniqlangan massivlarga mos keladi.
Satrni moslashtirish bilan algoritm quyidagicha realizatsiya qilinishi mumkin:
vector<int> simpleManacher(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)
}
vector<int> oddLengthManacher(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
int l = 1, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = max(0, 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);
}
vector<int> adjustedManacher(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
auto res = oddLengthManacher(t + "#");
return vector<int>(begin(res) + 1, end(res) - 1);
}