Два способа подсчета палиндромов

Было дело, возник вопрос: как посчитать количество палиндромов в строке. Напомню, что палиндром - строка, правая часть которой является зеркальным отображением левой. К примеру: abccba.

Первый способ - python way

Основная идея - сгенерировать все подстроки для данной строки, а затем определить, какая из них является палиндромом. Следующий код хорошо справляется с задачей:

    word = 'satorarepotennetoperarotas'
    words = set(word[i:j] for i in range(len(word)) for j in range(len(word),i,-1))

    for w in sorted(words,key=len):
        if w == ''.join(reversed(w)):
            print w

Одна ремарка - этот простой пример находит не совсем палиндромы: находятся все строки, которые читаются одинаково и в прямом, и в обратном направлении.

Второй способ - push down automata

Первый способ справляется замечательно. Однако, генерировать кучу подстрок и проверять их на "палиндромность" как-то скучно. Можно придумать способ веселее. Вспомним, что палиндромы описываются классом языков, называемых контекстно-свободными. Эти языки могут быть заданы двумя способами - либо контекстно-свободной грамматикой, либо механизмом под названием PDA (push down automata) - автомат с магазинной памятью.

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

Следующий код делает всю грязную работу.

# -*- coding: utf-8 -*-

def start(tape, stack, cargo):
    if not tape: return
    yield (start, tape[1:], stack[:], cargo)
    yield (pop, tape[:], stack[:], cargo)

def pop(tape, stack, cargo):
    if not tape: return
    if stack and tape[0] == stack[-1]:
        yield (push, tape[1:], stack[:-1], cargo + [tape[0]])       # Change state to 'push'
    yield (pop, tape[1:], stack + [tape[0]], cargo + [tape[0]])     # Loop

def push(tape, stack, cargo):
    if not stack:
        print .join(cargo)
    if tape and stack and stack[-1] == tape[0]:
        yield (push, tape[1:], stack[:-1], cargo + [tape[0]])       # Loop

def traverse(tape):
    agenda = []
    agenda.append((start, list(tape), [], []))
    while agenda:
        state, tape, stack, cargo = agenda.pop()
        for aid in state(tape, stack, cargo):
            agenda.append(aid)

traverse('satorarepotennetoperarotas')

Результат:

satorarepotennetoperarotas
atorarepotennetoperarota
torarepotennetoperarot
orarepotennetoperaro
rarepotennetoperar
arepotennetopera
repotennetoper
epotennetope
potennetop
otenneto
tennet
enne
nn

Здесь всего три состояния. Состояние start поглощает "лишние" символы и спонтанно переводит автомат в состояние pop. Состояние pop "забрасывает" символы на стек и спонтанно переходит на push. Последнее считывает символы со стека. Если это удается и стек опустошается (т.е. все символы на стеке считались в обратном порядке), то печатается результат, хранящийся в списке cargo.

Данный код не самый оптимальный и по скорости уступает первому (в питоновской реализации). Однако, он хорошо демонстрирует применимость PDA для работы с текстом. Данным способом можно реализовать довольно сложные схемы обработки.

Oбработка текста