Недетерминированные пушдаунные автоматы и палиндром

Question

Мне нужно найти палиндромы в тексте (слова имеют длину <= 6 и состоят из строчных и прописных букв) и использовать для этого Pushdown Automata, но, к сожалению, я не совсем знаком с этой темой.Может ли кто-нибудь объяснить мне, как я могу запрограммировать это?Или, может быть, какая-то статья или темы, где это было сделано.Буду рад каждому совету! </p>

Answer 1

Простым подходом может быть добавление флага в середине вашего слова.Начните вставлять каждый символ вашего слова в стек, пока не дойдете до флага.После достижения флага вы начинаете выталкивать символ из стека и сравнивать его со второй половиной вашего слова.

Если каждый символ в стеке соответствует каждому соответствующему символу во второй половине, ваше словоэто палиндром.Это простое решение, если вы понимаете это, вы также можете провести больше исследований для решения без флага.

Кроме того, я думаю, что ваша лучшая карта - взглянуть на другие ответы, такие как: Какпушиндром знает, как читать палиндром? , который очень хорошо объясняет, как автоматы работают с любой длиной палиндрома (четная и нечетная длина), поскольку мое решение будет работать только с четной длиной.