Manacher algoritmi berilgan satrda subpalindromlarni chiziqli vaqt ichida topish uchun ishlatiladi. Yanada rasmiyroq masala qo‘yilishi quyidagicha ko‘rinadi: Uzunligi n bo‘lgan s satri berilgan. s[i…j] ostsatri palindrom bo‘ladigan barcha (i,j) juftliklarni toping. t satri palindrom deyiladi, agar ( - uchun teskari satr).
t=trev
trev
t
Algoritm
Oddiy yondashuv
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.
Toq uzunlikdagi satr uchun Manacher algoritmi
dodd[i]i markazli toq uzunlikdagi palindromlarni bildirsin. (l,r) - topilgan eng o‘ngdagi (sub)palindromning chegaralari bo‘lsin (ya’ni joriy eng o‘ngdagi (sub)palindrom - s[l+1]s[l+2]…s[r−1]). Dastlab l=0,r=1, bu bo‘sh satrga teng.
Keyin biz dodd[i] ni hisoblamoqchimiz, shuning uchun:
Agar i joriy subpalindromdan tashqarida bo‘lsa, ya’ni i≥r, yuqorida tasvirlangan oddiy yondashuvdan foydalanishimiz mumkin.
Agar i≤r bo‘lsa, (l,r) subpalindromida i ning "oyna" pozitsiyasini topamiz, ya’ni j=l+(r−i) pozitsiyasini olamiz va
dodd[j] qiymatini tekshiramiz. j(l+r)/2 ga nisbatan i ga simmetrik pozitsiya bo‘lgani uchun, biz deyarli har doim dodd[i]=dodd[j] ni aniqlay olamiz. Buning illyustratsiyasi (j atrofidagi palindrom amalda i atrofidagi palindromga "ko‘chiriladi"):
….
Murakkab holat "ichki" palindrom "tashqi" palindrom chegaralariga yetib borganda bo‘lishi mumkin, ya’ni
j−dodd[j]≤l (yoki, xuddi shuning o‘zi,
i+dodd[j]≥r). "Tashqi" palindromdan tashqarida simmetriya kafolatlanmaganligi sababli, oddiy tayinlash
dodd[i]=dodd[j] noto‘g‘ri bo‘ladi: bizda i pozitsiyasidagi palindrom bir xil uzunlikka ega ekanini tasdiqlash uchun yetarli ma’lumot yo‘q.
Bunday vaziyatlar bilan to‘g‘ri ishlash uchun hozircha palindrom uzunligini cheklashimiz kerak, ya’ni dodd[i]=r−i, . Shundan so‘ng biz yuqorida tasvirlangan oddiy yondashuvni ishga tushiramiz, u imkon qadar
dodd[i] ni oshirishga harakat qiladi.
Bu holatning illyustratsiyasi (j markazli palindrom "tashqi" palindromga sig‘ishi uchun cheklanadi):
…palindromesl+1…sj…palindromesi−(r−i)+1…palindromebu yerga siljishga urinib ko‘ring……………….
Rasmda ko‘rsatilishicha, j markazli palindrom kattaroq bo‘lishi va "tashqi" palindromdan tashqariga chiqishi mumkin bo‘lsa-da, lekin markaz sifatida
i bilan biz faqat "tashqi" palindrom ichiga to‘liq sig‘adigan qismini ishlata olamiz. Ammo
i pozitsiyasi uchun javob (
dodd[i]) 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 dodd[i] hisoblangandan so‘ng (l,r) qiymatlarini yangilashimiz kerak.
Toq uzunlikdagi Manacher algoritmi uchun realizatsiya:
Umumiy holat uchun Manaker algoritmi
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 d[2i]=2deven[i]+1 va d[2i+1]=2dodd[i], bu yerda d#-qo‘shni satrda toq uzunlikdagi palindromlar uchun Manacher massivi, dodd va deven esa yuqorida asl satrda aniqlangan massivlarga mos keladi.
Satrni moslashtirish bilan algoritm quyidagicha realizatsiya qilinishi mumkin: