Има толкова много решения за това и най-доброто е да се реши с „алгоритъма на мениджъра“.
Пиша едно от решенията, което работи перфектно и е лесно за разбиране. Надявам се, че ще го разберете.
Имаме два случая, или палиндромът е с нечетна дължина или с четна дължина.
Например: даден низ s = “babad”, s1 =“cbbd”. Трябва да намерим най-дългия палиндромен подниз.
За низ s отговорът ще бъде „bab“, а за s1 е „bb“.
Помислете за празен низ, тук answer = “”,и приемете, че има най-голямата дължина. Сега и за двата случая, четна и нечетна дължина, ще намерим палиндромен подниз.
За нечетна дължина ще имаме един център, тоест само i, но това не е случаят за четна дължина. Имаме два центъра за проверка, i и i + 1.
За да намерим палиндром, ще създадем функция palindrome()и тя ще съдържа 3 параметъра, низ, ляв индекс и десен индекс. За нечетна дължина левият и десният индекс ще бъдат еднакви, но за четна дължина, ако левият е i, тогава десният ще бъде i + 1.
нечетен = палиндром(и, i, i) четен = палиндром(и, i, i+1)
Ако приемем, че левият и десният индекс са нула. Повторете цикъла, докато открием палиндром и върнем подниза.
Сега трябва да проверим дали дължината на нечетния низ е по-голяма от дължината на четния низ. Ако нечетното е по-голямо от четното, ще го присвоим на променлива с име large и след това ще проверяваме large с нашия празен низ, докато получим най-дългия палиндромен низ.
Надявам се, че сте разбрали това. Ако имате някакви съмнения, моля, коментирайте по-долу.
Благодаря, че прочетохте това.